deniok: (удивлён)
[personal profile] 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х это не канает. Жалко.


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

Date: 2008-02-12 06:47 am (UTC)
From: [identity profile] deni-ok.livejournal.com
А куда композитор делся? Который в Хаскелле (.), в комбинаторной логике B, а в лямбде \f g x -> f (g x)

Date: 2008-02-12 06:52 am (UTC)
From: [identity profile] deni-ok.livejournal.com
То есть
s' . id = (.) s' id = (\ f g x -> f (g  x) ) s' id = \x -> s' (id x) = ...

Date: 2008-02-12 07:01 am (UTC)
From: [identity profile] ilya-portnov.livejournal.com
Угу, с дополнительным оператором в середине оно конечно всё по-другому будет. Но в лямбде ведь применить одну функцию к другой можно и без всяких "композиторов". Что я и проделал выше. Точку только вот зря там поставил... ;)

Date: 2008-02-12 07:26 am (UTC)
From: [identity profile] 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 не сделать. Вобщем, о том и речь - неуниверсально это...

Profile

deniok: (Default)
deniok

February 2022

S M T W T F S
  12345
6789101112
13141516171819
20212223 242526
2728     

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 10th, 2025 08:42 am
Powered by Dreamwidth Studios