Стой

Но в типах нет лямбд

ListF a b = NilF | ConsF a b List a = Fix(ListF a)

Ну да

Точно

давай теперь вспомним что у нас было про ф алгебры

Зачем лямбды, еслм можно сделать мусорный тип

нам нужны алгебры для этого

Зачем лямбды, еслм можно сделать мусорный тип

где лямбды?

У меня была мысль, что ты хочешь сделать типа data List a = Fix (\b -> Nil | Cons a b)

нет

Ты так и сделал

Просто вынес в отдельный тип

ну наша задача научится строить рекурсию без рекурсии, индуктивные типы без индукции

ща к катаморфизмам анаморфизмам прийдем)

коммутативные диаграммы читать умеешь?

Более менее

Вот эту не понимаю

у нас есть Fix :: f(Fix f) -> Fix (f) и unFix :: Fix f -> f(Fix f)

А, ну дошло

у них изоморфизм (больше об этом - лемма Ламбека)

а значит мы можем их смело подменять

ах

я уже тут написал все для h

У тебя уже были готовы эти схемы или ты их как-то быстро строишь?)

да я делаю потихоньку)

ну так вот

Слушай, я правильно понимаю, что функтор морфизма - морфизм из fa в f b?

у нас есть h = alg . fmap h . unFix

Слушай, я правильно понимаю, что функтор морфизма - морфизм из fa в f b?

вроде да

f : a -> b F(f) : F a -> F b

ну вот эта вот h

есть катаморфизм

ща другой ракурс

Ну да, свертка

Ну да, свертка

более общее ее понятие (свертка любой фигни)

cata alg = alg . fmap h . unFix

теперь можно писать свертку без рекурсий

любую

например сумма

первым делом сделаем паттеры (так красивее будет для case)

pattern N = Fix NilF pattern C x y = Fix(ConsF x y)

дальше это должно быть функтор! у нас же функторная алгебра

instance Functor (ListF t) where fmap _ NilF = NilF fmap f (ConsF a b) = ConsF a (f b)

aaaaa

Чет не так

Ты что-то не то мапишь же

Ты что-то не то мапишь же

че это?

sumL :: Num a => List a -> a sumL = cata go where go = \case NilF -> 0 ConsF a b -> a + b

где рекурсия?)))

go это наша алгебра вида go :: Num a => ListF a a -> a

А, я понял

Моноид некий

как бы у ListF a a хвост у этого будет уже собранная инфа в типа a

Моноид некий

не моноид)

анаморфизм есть дуализм к катаморфизму

хиломорфизм (отец всех морфизмов) есть их композиция

функторная {ко}алгебра прекрасна

можно просто сдохнуть?

чего?

cata alg = alg . fmap h . unFix

А откуда h?

он давно с нами

А откуда h?

сорри провтыкал)

cata alg = alg . fmap alg . unFix

ERROR: S client not available

но ты это мог бы сам по диаграмме восстановить

Во

Другое дело

Не мог бы

Мало понимания

pattern N = Fix NilF pattern C x y = Fix(ConsF x y)

для этого нужно включить прагму PatternSynonyms

Но кажется, суть в том, что a : (b : c) превращается в a : (b + c)

pattern N = Fix NilF pattern C x y = Fix(ConsF x y)

А для чего это вооьще?

Нигде же не использовалось

Но кажется, суть в том, что a : (b : c) превращается в a : (b + c)

А это возможно только потому что в нашем типе не захардкорено, что b - список, поэтому мы можем егл смапить

Я, внезапно, все понял

newtype Fix f = Fix { unFix :: f(Fix f) } data ListF a b = NilF | ConsF a b type List a = Fix(ListF a) instance Functor (ListF t) where fmap _ NilF = NilF fmap f (ConsF a b) = ConsF a (f b) instance Show t => Show (List t) where show = (<>"]") . ("["<>) . cata alg where alg NilF = "" alg (ConsF x []) = show x alg (ConsF x xs) = show x <> "," <> xs cata psi f = psi . fmap f . unFix sumL :: Num a => List a -> a sumL = cata go where go :: Num a => ListF a a -> a go = \case NilF -> 0 ConsF a b -> a + b

Кроме того, зачем это нужно

Но это интересно

мы можем сделать любой индуктивный тип например Expression

А для чего это вооьще?

ща до anamorphism дойдем

как я и говорил в дуальных алгебрах надо только стрелки поменять местами (направление)

newtype Fix f = Fix { unFix :: f(Fix f) } data ListF a b = NilF | ConsF a b type List a = Fix(ListF a) instance Functor (ListF t) where fmap _ NilF = NilF fmap f (ConsF a b) = ConsF a (f b) instance Show t => Show (List t) where show = (<>"]") . ("["<>) . cata alg where alg NilF = "" alg (ConsF x []) = show x alg (ConsF x xs) = show x <> "," <> xs cata psi f = psi . fmap f . unFix sumL :: Num a => List a -> a sumL = cata go where go :: Num a => ListF a a -> a go = \case NilF -> 0 ConsF a b -> a + b

f в cata не передается, а передавать ничего в sum не нужно

f в cata не передается, а передавать ничего в sum не нужно

чего?

Ты передаешь в ката только пси

да

cata f = f . fmap (cata f) . unFix

сорри

просто я упорот и делал так раньше))) cataRec f = fix(cata f)

я думаю у тебя это уже должно заработать)

и вывести сумму

Я с телефона, возможность проверить будет только завтра

На телефоне даже репл.ит не раьотает

перейдем к анаморфизму?

Давай

ката - разрушать (свертка в общем общих случаев) ана - (развертка в общем общих случаев)