Monadability

[lomeo]

Рассматривая тип data S a = S a (S a) я увидел, что его нельзя сделать монадой - не будет работать либо первый, либо второй закон монад. Кто знает, есть ли какие то правила, позволяющие вычислить (или хотя бы почувствовать), что такой то тип не может быть монадой?

Comments

[ex-ex-zhuzh.livejournal.com]

это же тип бесконечных списков, разве нет? почему же нельзя? может, расскажете, а то что-то лень считать ;))

[lomeo.livejournal.com]

data S a = S a (S a)

return можно реализовать только как (всякие bottom отбрасываем, разумеется)

return x = S x (return x)

Тогда первый закон
return x >>= f == f x
или
(S x (return x)) >>= f == f x

Т.к. тип x :: forall a. a, то нам можно только вытащить x из одного места этого потока. Логично предположить (первое допущение), что это первый элемент (это второе допущение в написании монады). Первый закон тогда работает, а второй нет:

m >>= return == m
m@(S x xs) >>= return = return x /= m

И всё было бы хорошо, если бы (см. первое допущение) можно было бы делать операцию объединения нескольких потоков в один. Как у списка concat. Но нельзя из-за их бесконечности. Поэтому первое допущение работает. А следовательно монаду на этом типе реализовать нельзя.

[lomeo.livejournal.com]

Пардон, первое допущение, это то, что "нам МОЖНО ТОЛЬКО вытащить x из одного места этого потока". Просто потому что нет операции S (S a) -> S a, сохраняющей ВСЕ элементы вложенных потоков (из-за их беконечности).

[lomeo.livejournal.com]

Во! Кстати! Что есть join для этой монады? Нету join-а! Значит, нет и монады.

[ex-ex-zhuzh.livejournal.com]

ну, такую операцию можно придумать, напр. взять диагонализацию вроде канторовой. чем не join?

[lomeo.livejournal.com]

Я не знаю, что такое канторовая диаганолизация, мне тут на #haskell подсказали (1,1) (2,1) (1,2) (3,1) (2,2) (1,3) (4,1) (3,2) (2,3) (1,4)

Оно? Если да, то первый закон не работает :-/
Тут в чём проблема, чтобы (return x) >>= f был равен f x

Т.е. есть у нас бесконечное кол-во одинаковых (?) бесконечных списков

1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

и нам надо из них получить один 1 2 3 4 5.

За невежество извиняюсь, не подумал о том, что можно так собрать.

[lomeo.livejournal.com]

Я гоню, Cale подсказал как можно сделать монаду:

data S a = S a (S a)

headS (S x _) = x
tailS (S _ x) = x

toList (S x xs) = x : toList xs

instance Functor S where
    fmap f (S x xs) = S (f x) (fmap f xs)

instance Monad S where
    return x = S x (return x)
    m >>= f = joinS $ fmap f m
        where
            joinS (S (S x _) s) = S x (joinS (fmap tailS s))

Все три закона работают. Выбираем диагональные элементы (правда меня коробит, что элементы теряются). Об этом шла речь?

[ex-ex-zhuzh.livejournal.com]

ага, а вот fail придумать нельзя.

[thesz.livejournal.com]

Занес в мемориз, чтобы не потерять.