www.jammni.de

Gepostet:
16.06.2012 14:05

Umdrehen von Listen

Ich habe disen Code zum Drehen von Listen geschrieben und verstehe die Fehlermeldung von Hugs nicht. Ich habe schon diverse Sache ausprobiert aber es hat nichts geklappt.


schubse :: [a] -> [a]
schubse [x] = [x]
schubse (x:xe) = schubse xe : x

Fehlermeldung:


ERROR \"schubse.hs\":3 - Type error in application
*** Expression     : schubse xe : x
*** Term           : schubse xe
*** Type           : [[a]]
*** Does not match : a
*** Because        : unification would give infinite type

Zum Seitenanfang

Landei

Gepostet:
18.06.2012 14:46

Das Problem liegt bei schubse xe : x. Der : Operator erwartet links ein Element (du gibst ihm eine Liste) und rechts eine Liste (du gibst ihm ein Element). Eine mögliche Lösung wäre stattdessen schubse xs ++ [x].

Allerdings hat diese naive Lösung eine wirklich furchtbare Performance (versuche mal, den Ablauf für eine vierelementige Liste oder so nachzuvollziehen), und könnte z.B. mit einem Akkumulator oder durch Verwendung einer Fold-Funktion wesentlich verbessert werden.

Zum Seitenanfang

Xan

Gepostet:
19.06.2012 00:04

Vielen Dank. Es funktioniert.

Zum Seitenanfang

Landei

Gepostet:
19.06.2012 08:28

Deine Implementierung hat übrigens noch einen Schönheitsfehler: Du kannst keine leeren Listen drehen

Hier noch einmal die Version mit Akkumulator:


rev xs = go xs [] where
  go [] acc = acc
  go (x:xs) acc = go xs (x:acc)

Im Prinzip furchtbar einfach: Die Hilfsfunktion go stapelt das erste Argument ab und das zweite Argument (den Akkumulator) auf. Wenn nicht mehr zum Umstapeln da ist, gibt sie das zweite Argument zurück.

Die Version mit einem Fold sieht so aus:


import Data.List
rev = foldl\' (flip (:)) [] 

--oder ausfuehrlicher:
rev xs = foldl\' (\\ys y -> y:ys) [] xs

Zum Seitenanfang

Haskell-Forum