Запись zip (longzip) с использованием анаморфизма

Question

Работаю над проектом и пытаюсь написать лонгзип с использованием анаморфизма. У меня возникли проблемы с написанием коалгебры для этого варианта использования. Я определил свой анаморфизм в терминахFixниже:

      -- Fixed point of a Functor    
newtype Fix f = In (f (Fix f))     
    
deriving instance (Eq (f (Fix f))) => Eq (Fix f)    
    
out :: Fix f -> f (Fix f)    
out (In f) = f 

-- Anamorphism
type Coalgebra f a = a -> f a

ana :: (Functor f) => Coalgebra f a -> a -> Fix f
ana f = In . fmap (ana f) . f

Это определение происходит от «переворачивания стрелок» ката:

      -- Catamorphism    
type Algebra f a = f a -> a    
    
cata :: (Functor f) => Algebra f a -> Fix f -> a

cata f = f . fmap (cata f) . out

Я видел написанное с использованием версии ana, которая явно определена по-другому (принимает предикат в качестве параметра):

       zip2 = ana unsp fin
    where
    fin (as,bs) = (as==[]) || (bs ==[]) 
    unsp ((a:as), (b:bs)) = ((a,b),(as,bs))

(Взято с https://en.wikipedia.org/wiki/Anamorphism )

Но я не уверен, как двигаться дальше, используя версиюanaопределено выше, особенно в отношении написанияCoalgebraтипаa -> fa. Например, нужно ли было бы использовать два параметра списка дляzipи объединить их в одинa?

Answer 1

Во-первых, дайте себе отправную точку. Напишите, что вы собираетесь делать:

      -- make this example actually complete
{-# Language StandaloneDeriving, UndecidableInstances, DeriveFunctor #-}
import Prelude hiding (zip)


-- Fixed point of a Functor
newtype Fix f = In (f (Fix f))

deriving instance (Eq (f (Fix f))) => Eq (Fix f)
deriving instance (Show (f (Fix f))) => Show (Fix f)

out :: Fix f -> f (Fix f)
out (In f) = f

-- Anamorphism
type Coalgebra f a = a -> f a

ana :: (Functor f) => Coalgebra f a -> a -> Fix f
ana f = In . fmap (ana f) . f


-- Base functor for a list
data ListF a f = Nil | Cons a f deriving (Eq, Show, Functor)
type List a = Fix (ListF a)

-- write down the type. It helps you think about things
zip :: List a -> List b -> List (a, b)
zip x y = ana undefined undefined

Вы знаете, должно быть реализовано как вызовana, так что осталось выяснить семя и коалгебру. Должно быть достаточно ясно, что семя должно содержатьxиy. Не похоже, что какая-либо дополнительная информация необходима, так что давайте просто предположим, что начальное число будет(x, y)пока/если это не создаст проблемы. Этой информации достаточно, чтобы определить типы для этой первой попытки:

      zip :: List a -> List b -> List (a, b)
zip x y = ana zipCoalgebra (x, y)

zipCoalgebra :: (List a, List b) -> ListF (a, b) (List a, List b)
zipCoalgebra = undefined

Я чувствую, что это шаг, который вы пропустили: запишите, что вы пытаетесь сделать, и следуйте типам, чтобы определить, что вам нужно. Остальное кажется тривиальным, если вы когда-либо видели реализацию . Это вопрос написания самой скучной вещи, которая проверяет тип (обращая пристальное внимание на разницу междуListиListFв типе). Я настоятельно рекомендую вам прекратить читать здесь и попробовать сами. Я не могу сказать больше ничего, что действительно помогло бы научиться думать об этом.

Если вы действительно понятия не имеете:

      zipCoalgebra :: (List a, List b) -> ListF (a, b) (List a, List b)
zipCoalgebra (In (Cons a as), In (Cons b bs)) = Cons (a, b) (as, bs)
zipCoalgebra _ = Nil

Это действительно то, что вы ожидаете, если вы когда-либо видели реализациюzipпрежде, с необходимым шумом, чтобы сделать проверку типа вокругFix. Давайте попробуем:

      ghci> zip (In (Cons 1 (In Nil))) (In Nil)
In Nil
ghci> zip (In (Cons 1 (In Nil))) (In (Cons 2 (In Nil)))
In (Cons (1,2) (In Nil))

Ага. Ведет себя как ожидалось. Кажется, двух списков было достаточно в качестве затравки, и все в порядке.