Das ist,inits "abc" == ["","a","ab","abc"]

Es gibt eine Standardversion voninits imData.List, aber unten habe ich selbst eine Version geschrieben:

myInits = f id
 where
  f start (l:ls) = (start []):(f (start . (l:)) ls)
  f start [] = [(start [])]

Während meine Version etwas einfacher ist als die Standardversion, denke ich, ist sie aus Effizienzgründen nicht so gut. Ich vermute, dass, wennmyInits l ist vollständig ausgewertet es dauertO(n^2) Platz. Nehmen Sie zum BeispielmyTails, eine Implementierung vontails:

myTails a@(_:ls) = a:(myTails ls)
myTails [] = [[]]

Was ist fast genau das gleiche wie die Standardversion und ich vermute erreichtO(n) space durch Wiederverwenden der Listenenden.

Könnte jemand erklären:

Warum meine Version voninits ist schlechtWarum ist ein anderer Ansatz besser (entweder der Standard inData.List oder deine eigene).