Monadability

[lomeo]

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

Comments

[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))

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