Effizienterer Schwanz der Kirche codierte Liste

Question

Dies ist ein literarischer Haskell Beitrag. Speichern Sie es einfach als "ChurchList.lhs", um es auszuführen.

> {-# LANGUAGE Rank2Types #-} 

Eine Church-codierte Liste ist eine Möglichkeit, eine Liste über eine Funktion darzustellen. Es ähnelt sowohl dem Folding als auch dem Fortsetzungsstil.

> newtype ChurchList a = CList {runCList :: forall r. (a -> r -> r) -> r -> r} 

Zur Veranschaulichung, wie diese zu einer Liste entspricht, ist hier ein O (n) Isomorphismus

> fromList :: [a] -> ChurchList a 
> fromList xs = CList $ \cons empty -> foldr cons empty xs 

> toList :: ChurchList a -> [a] 
> toList cl = runCList cl (:) [] 

> instance Show a => Show (ChurchList a) where 
> show cl = "fromList " ++ show (toList cl) 

Diese Dinge haben eine gute Leistung charecteristics.

> singleton :: a -> ChurchList a -- O(1) 
> singleton a = CList $ \cons empty -> a `cons` empty 
> append :: ChurchList a -> ChurchList a -> ChurchList a -- O(1)!!! This also means cons and snoc are O(1) 
> append cl1 cl2 = CList $ \cons empty -> runCList cl1 cons (runCList cl2 cons empty) 
> concatCl :: ChurchList (ChurchList a) -> ChurchList a -- O(n) 
> concatCl clcl = CList $ \cons empty -> runCList clcl (\cl r -> runCList cl cons r) empty 
> headCl :: ChurchList a -> Maybe a -- O(1) 
> headCl cl = runCList cl (\a _ -> Just a) Nothing 

Jetzt kommt das Problem mit tail.

> tailClbad :: ChurchList a -> Maybe (ChurchList a) --O(n)?!! 
> tailClbad cl = (fmap snd) $ runCList cl 
> 
> (\a r -> Just (a, case r of 
> Nothing -> CList $ \cons empty -> empty 
> Just (s,t) -> append (singleton s) t)) --Cons 
> 
> Nothing --Empty 

Im Wesentlichen was meine Implementierung tut, ist die Liste in Kopf und Schwanz aufgeteilt. Cons ersetzt den Kopf und fügt den alten Kopf an den Schwanz an. Dies ist ziemlich ineffizient. Es scheint, dass Church Lists im Allgemeinen beim Aufspalten ineffizient sind.

Ich hoffe, dass ich falsch liege. Gibt es eine Implementierung von tailCl, die besser ist als O (n) (vorzugsweise O (1)).

Answer 1

Ja, es ist O (n). Eine kirchlich kodierte Liste wird mit ihrer foldr-Funktion identifiziert, die überall dasselbe tun muss. Da es für den ersten Gegenstand erforderlich ist, etwas für den ersten Gegenstand zu tun, muss für alle übrigen Gegenstände dasselbe getan werden.

Ihre Lösung ist so produktiv wie möglich. Die gleiche Lösung kann auch trivial geschrieben werden, indem eine Liste erstellt und auf den ersten Artikel abgestimmt wird.

safeTail :: [a] -> Maybe [a] 
safeTail []  = Nothing 
safeTail (_:xs) = Just xs 

tailCtrivial :: ChurchList a -> Maybe (ChurchList a) 
tailCtrivial = fmap fromList . safeTail . toList 

Answer 2

Papier Church Encoding of Data Types Considered Harmful for Implementations von Koopman, Plasmeijer und Jansen scheint sich mit dem Thema ausführlich zu beschäftigen. Insbesondere unter Angabe der abstrakten (Hervorhebung von mir):

[...]

Wir zeigen, dass in der Kirche Codierung Selektoren von Konstrukteuren der rekursiven Typ ergibt, wie die Schwanz einer Liste , haben eine unerwünschte Strenge in der Wirbelsäule der Datenstruktur. Die Scott-Kodierung behindert in keiner Weise die faule Auswertung. Die Auswertung der rekursiven Wirbelsäule durch die Kirche Codierung macht die Komplexität von diese Destruktoren O (n). Die gleichen Destruktoren in der Scott Codierung erfordert nur konstante Zeit. Außerdem hat die Church-Kodierung ernste Probleme mit der Graphenreduktion. Die Parigot-Codierung kombiniert das Beste aus beiden Welten, aber in der Praxis bietet dies keinen Vorteil .

Doch während Scott encoding den Leistungsvorteil bietet, scheint es problematic zu sein, um es ohne Zusatz von rekursiven Typen in System F zu definieren.

Answer 3

Nein, nicht notwendigerweise O (n):

Prelude> 5 nehmen. snd. foldr (\ a r-> (a: fst r, fst r)) ([], undefined) $ [1 ..]
[2,3,4,5,6]

es in der Tat fügt O (1) Overhead für jeweils Element schließlich hinzu.

Der Versuch, für die safetail hat nicht funktioniert:

Prelude> fmap (take 5). snd. foldr (\ a r-> (fmap (a :) $ fst r, fst r)) (Just [], Nothing)
$ [1 ..]
Unterbrochen.

So

tailCL cl = CList $ \k z-> snd $ runCList cl (\a r-> (a`k`fst r,fst r)) (z, undefined) 

Prelude> 5 nehmen. auflisten . SchwanzCL. fromList $ [1 ..]
[2,3,4,5,6]

---

edit: Kommentar followng von @user3237465, stellt sich heraus, dass safetail möglich ist, nachdem alle :

Auftakt> fmap (take 5). snd. foldr (\ a ~ (r, _) -> (Nur (a: fromJust r), r)) (Just [] , Nichts) $ [1 ..]
Nur [2,3,4,5, 6]

Der Grund ist es vorher nicht funktioniert ist, dass Maybe ‚s fmap Kräfte zweites Argument, um herauszufinden, welcher Fall ist es, aber hier wir wissen, dass es einen Just Wert, durch den Bau. Ich konnte es aber nicht als Definition für deinen Typ definieren, was auch immer ich versuchte, bestand den Typ Checker nicht.