Убогонькая единичка

[deniok]

По поводу сегодняшнего LtU: S has a left inverse

Shin-Cheng Mu типа открыл обратный к S комбинатор:

-- классический коннектор
s :: (a -> b -> c) -> (a -> b) -> a -> c
s = \ f g x -> f x (g x)
-- обратный к нему
s' :: ((a -> b) -> a -> c) -> a -> b -> c
s' = \ f x y -> f (const y) x

Shin-Cheng Mu пишет, что

s' . s = id

и я губу-то и раскатал.

Увы, всё не так сладко. Если вывести тип

(s' . s) :: (a -> b -> c) -> a -> b -> c

то видно, что это - ограниченная версия id с более частным principle type, чем настоящая id. То есть

(s' . s) (++)  == (++)
(s' . s) foldr == foldr

но для арности меньшей 2х это не канает. Жалко.


ЗЫ: я где-то видел статью каких-то итальянцев, доказывавших, что обращение комбинаторов в общем случае невозможно, но ссылку посеял.

Comments

[ilya-portnov.livejournal.com]

Угу, с дополнительным оператором в середине оно конечно всё по-другому будет. Но в лямбде ведь применить одну функцию к другой можно и без всяких "композиторов". Что я и проделал выше. Точку только вот зря там поставил... ;)

[deni-ok.livejournal.com]

Ага, понял

s' id = flip const

Но это не универсально. s' из-за const в своём определении затирает часть информации безвозвратно:

Prelude> :t (s' map)
(s' map) :: [b] -> a -> [a]

Применим к массиву символов и числу

Prelude> (s' map) "abcd" 1
[1,1,1,1]

Опс - символы пропали. С map, к тому же, конструкцию (s' map) s не сделать. Вобщем, о том и речь - неуниверсально это...