[Haskell] Welke denkfout maak ik hier ?

[Aaargh!]

Ik heb hier een opdracht waar ik niet uit kom, ik zit er al een tijdje mee te prutsen en ik word er helemaal gek van.

give the type of and define a function 'iter' so that

code:

iter n f x = f ( f  ... ( f x ) ... ) )

where f occurs n times on the right-hand side of the equation. For instance we should have

code:

iter 3 f x = f ( f ( f x ) )

and iter 0 should return x.

Nu had ik zelf het volgende bedacht:

code:

iter :: Int -> (a -> a) -> a -> a
iter n f x | n == 0 = x
           | otherwise = f (iter n-1 f x)

Maar dit geeft de error:

code:

ERROR "9.9.hs":2 - Inferred type is not general enough
*** Expression    : iter
*** Expected type : Int -> (a -> a) -> a -> a
*** Inferred type : Int -> (((a -> a) -> a -> a) -> (a -> a) -> a -> a) -> ((a -> a) -> a -> a) -> (a -> a) -> a -> a

Is hier iemand die inziet welke denkfout ik maak en hoe de functie wel moet (en waarom) ?

[ Voor 12% gewijzigd door Aaargh! op 07-01-2006 19:24 ]

[Aaargh!]

Bug gevonden met behulp van #haskell op freenode.

applicatie functies gaan voor simpele operatoren, het antwoord is dus:

code:

iter :: Int -> (a -> a) -> a -> a
iter n f x | n == 0 = x
           | otherwise = f (iter (n-1) f x)

[Verwijderd]

Is dit niet logischer?

code:

iter :: Int -> (a -> a) -> a -> a
iter n f x | n == 0 = x
           | otherwise = iter (n-1) f (f x)

Van een iteratieve taal is bekend dat staartrecursie ietwat efficienter is. Zou dat ook voor functionele talen gelden?

[Verwijderd]

Waarom gebruik je in plaats van expliciete recursie geen standaardfuncties?

Haskell:

iter :: Int -> (a -> a) -> a -> a
iter n f x = foldr (.) x (replicate n f)

Dit klopt nog niet helemaal, maar je begrijpt wat ik bedoel Ik ben erachter wat er fout aan is, op de manier zoals het hier boven staat krijg je iets als:

Haskell:

f . f . f . 3

Dat is natuurlijk niet goed aangezien het type van f en 3 niet overeenkomen voor de functie compositie operator (.). Daarom moet er een foldr1 worden gebruikt en dan kan het wel:

Haskell:

iter :: Int -> (a -> a) -> a -> a
iter n f x = foldr1 (.) (replicate n f) $ x

[ Voor 49% gewijzigd door Verwijderd op 08-01-2006 14:41 ]

[twanvl]

Als je fold wilt gebruiken dan kan dat met ($), de functie applicatie operator.
Ik kan me voorstellen dat de aargh's code inzichtelijker is, vooral voor beginners. Om het nog duidelijker te maken kan je beter patern matching gebruiken in plaats van expliciete tests:

code:

iter :: Int -> (a -> a) -> a -> a
iter 0 f x = x
iter n f x = iter (n-1) f (f x)  -- of f (iter (n-1) f x)

[Verwijderd]

Ik wil nog wel even opmerken dat mijn oplossing nog niet helemaal correct is:

Haskell:

iter :: Int -> (a -> a) -> a -> a
iter n f x = foldr1 (.) (replicate n f) $ x

Een foldr1 kan namelijk niet worden toegepast op een lege lijst, en bij een lege lijst moet slechts x worden opgeleverd. Dit kan je simpel afvangen met een pattern match maar dat is natuurlijk niet mooi Ik ga nog op zoek naar een oplossing in termen van standaardfuncties die helemaal correct is..

[Infinitive]

In plaats van foldl1 de functie foldl gebruiken met x als initieel element?
Geen idee of het werkt, aangezien ik even langs kwam schieten en geen gelegenheid heb om nu het topic door te lezen

[ Voor 28% gewijzigd door Infinitive op 08-01-2006 21:18 ]