How would you (re)implement iterate in Haskell?

Question

iterate :: (a -> a) -> a -> [a]

(As you probably know) iterate is a function that takes a function and starting value. Then it applies the function to the starting value, then it applies the same function to the last result, and so on.

Prelude> take 5 $ iterate (^2) 2
[2,4,16,256,65536]
Prelude>

The result is an infinite list. (that's why I use take). My question how would you implement your own iterate' function in Haskell, using only the basics ((:) (++) lambdas, pattern mataching, guards, etc.) ?

(Haskell beginner here)

emi · Accepted Answer · 2010-09-22 13:54:46Z

30

Well, iterate constructs an infinite list of values a incremented by f. So I would start by writing a function that prepended some value a to the list constructed by recursively calling iterate with f a:

iterate :: (a -> a) -> a -> [a]
iterate f a = a : iterate f (f a)

Thanks to lazy evaluation, only that portion of the constructed list necessary to compute the value of my function will be evaluated.

edited Sep 22, 2010 at 13:54

answered Sep 22, 2010 at 13:42

emi

5,4301 gold badge29 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

QuantumKarl Over a year ago

This looks like the a variation of the "fix" definition "fix f = f (fix f)" similar to ..."iterate f (f a)" you could use fix to define iterate: "iterate f a = fix (\r x -> x:r (f x) ) a" not that its any better, just thought id say :)

sclv · Accepted Answer · 2011-06-02 03:15:56Z

15

Also note that you can find concise definitions for the range of basic Haskell functions in the report's Standard Prelude.

Reading through this list of straightforward definitions that essentially bootstrap a rich library out of raw primitives can be very educational and eye-opening in terms of providing a window onto the "haskell way".

I remember a very early aha moment on reading: data Bool = False | True.

edited Jun 2, 2011 at 3:15

answered Sep 22, 2010 at 14:46

sclv

39k7 gold badges102 silver badges208 bronze badges

Comments

MaroonSphinx · Accepted Answer · 2024-06-01 00:31:07Z

1

You've already been given the simplest possible implementation of it; however, there are other ways.

One way is to use a higher order function, like so:

import Data.List (unfoldr)

iterate f x = unfoldr (\x -> Just (x, f x)) x

The function unfoldr is a higher-order function meant for creating lists. Here's the most straightforward implementation of it:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr step b = case step b of 
  Nothing -> []
  Just (a, b') -> a : unfoldr step b'

In the same way that foldr abstracts of the direct recursion of reducing lists, unfoldr abstracts over the direct recursion of creating them.

answered Jun 1, 2024 at 0:31

MaroonSphinx

1371 silver badge7 bronze badges

Comments

natka_m · Accepted Answer · 2024-11-20 00:07:48Z

1

This is not precisely an answer to the question asked, because there are higher-order functions from Prelude and the base library involved, but I just came across a Haskell wiki page which presents some further ways in which iterate can be implemented:

iterate f x = scanl f x (repeat x)
iterate f x = scanl1 f (repeat x)
iterate f x = fix ((x:) . map f)

answered Nov 20, 2024 at 0:07

natka_m

1,70122 silver badges28 bronze badges

Collectives™ on Stack Overflow

How would you (re)implement iterate in Haskell?

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related