CODEWITHSUNDEEP
haskell
Kim Bogdan Fransson
Kim Bogdan Fransson

Reputation: 67

Insufficient definition of replicate

I have a question that I think is rather tricky.

The standard prelude contains the function

replicate :: Int -> a -> [a]

The following might seem like a reasonable definition for it

replicate n x = take n [x,x,..]

But it is actually not sufficient. Why not?

I know that the replicate function is defined as:

replicate        :: Int -> a -> [a]       
replicate n x    =  take n (repeat x)

And repeat is defined as:

repeat           :: a -> [a]  
repeat x         =  xs where xs = x:xs

Is the definition insufficient (from the question) because it uses an infinite list?

Upvotes: 3

Views: 153

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477210

First of all there is a small syntax error in the question, it should be:

replicate n x = take n [x,x..]
--                         ^ no comma

but let's not be picky.

Now when you use range syntax (i.e. x..), then x should be of a type that is an instance of Enum. Indeed:

Prelude> :t \n x -> take n [x,x..]
\n x -> take n [x,x..] :: Enum a => Int -> a -> [a]

You can argue that x,x.. will only generate x, but the Haskell compiler does not know that at compile time.

So the type in replicate (in the question) is too specific: it implies a type constraint - Enum a - that is actually not necessary.

Your own definition on the other hand is perfectly fine. Haskell has no problem with infinite lists since it uses lazy evaluation. Furthermore because you define xs with xs as tail, you actually constructed a circular linked list which also is better in terms of memory usage.

Upvotes: 6

Related Questions