5

Kilise kodlaması için cata paketini recursion-schemes paketinden kullanabilmek istiyorum.Kilise kodlu listeler için Catamorphisms

type ListC a = forall b. (a -> b -> b) -> b -> b 

Kullanışlılık açısından ikinci bir sıralama türü kullandım, ama umrumda değil. Gerekli olduğunu düşünüyorsanız, newtype'u eklemekten, GADT'leri vb. Kullanmaktan çekinmeyin.

Kilise kodlama fikri yaygın olarak bilinen ve basit olan:

three :: a -> a -> a -> List1 a 
three a b c = \cons nil -> cons a $ cons b $ cons c nil 

Temelde "soyut belirtilmemiş" cons ve nil yerine "normal" kurucular kullanılır. Herşeyin bu şekilde kodlanabileceğine inanıyorum (Maybe, ağaçlar, vb.).

toList :: List1 a -> [a] 
toList f = f (:) [] 

fromList :: [a] -> List1 a 
fromList l = \cons nil -> foldr cons nil l 

Yani onun baz funktoru listelerinin aynı olduğunu ve bunun için project uygulamak ve gelen makine kullanmak mümkün olmalıdır:

O List1 Normal listelere gerçekten izomorf olduğunu göstermek kolaydır recursion-schemes.

Ama yapamadım, bu yüzden sorum şu: "Bunu nasıl yaparım?". Normal listeleri için elimden sadece desen maç:

decons :: [a] -> ListF a [a] 
decons [] = Nil 
decons (x:xs) = Cons x xs 

Ben fonksiyonları üzerindeki desen maç, ben listeyi yapısızlaştırmak bir kat kullanmak zorunda beri.

decons2 :: [a] -> ListF a [a] 
decons2 = foldr f Nil 
    where f h Nil = Cons h [] 
     f h (Cons hh t) = Cons h $ hh : t 

Ancak kilise kodlu listelerden uygun hale getirmek için başarısız oldu:

-- decons3 :: ListC a -> ListF a (ListC a) 
decons3 ff = ff f Nil 
    where f h Nil = Cons h $ \cons nil -> nil 
     f h (Cons hh t) = Cons h $ \cons nil -> cons hh (t cons nil) 

cata sahiptir aşağıdaki imzayı:

cata :: Recursive t => (Base t a -> a) -> t -> a 
Bir kat bazlı Normal listeler için project yazabilirsiniz

Listelerimle kullanmak için şunlara ihtiyacım var:

  1. Hem adımların başarısız instance Recursive (List a) where project = ...

uygulamak için type family instance Base (ListC a) = ListF a

  • kullanarak listesi için üs funktoru türü ilan etmek.

  • +0

    Başarınız nedir? Bunu denedim (kolaylık için 'newtype' ekleme) ve iyi çalışıyor. – MigMit

    +0

    Sorumu güncelledim – nponeccop

    +1

    'newtype', sadece bir kolaylık değil, aynı zamanda gerekli olduğu ortaya çıktı. Kod şimdi çalışıyor. – nponeccop

    cevap

    4

    newtype sarıcı, kaçırdığım en önemli adım olduğu ortaya çıktı. İşte recursion-schemes dan örnek bir katamorfizma ile birlikte kod.

    {-# LANGUAGE LambdaCase, Rank2Types, TypeFamilies #-} 
    
    import Data.Functor.Foldable 
    
    newtype ListC a = ListC { foldListC :: forall b. (a -> b -> b) -> b -> b } 
    
    type instance Base (ListC a) = ListF a 
    
    cons :: a -> ListC a -> ListC a 
    cons x (ListC xs) = ListC $ \cons' nil' -> x `cons'` xs cons' nil' 
    nil :: ListC a 
    nil = ListC $ \cons' nil' -> nil' 
    
    toList :: ListC a -> [a] 
    toList f = foldListC f (:) [] 
    fromList :: [a] -> ListC a 
    fromList l = foldr cons nil l 
    
    instance Recursive (ListC a) where 
        project xs = foldListC xs f Nil 
        where f x Nil = Cons x nil 
          f x (Cons tx xs) = Cons x $ tx `cons` xs 
    
    len = cata $ \case Nil -> 0 
            Cons _ l -> l + 1