Haskell: recursive Replicate function

Question

I'm just getting started with Haskell. I'm trying to create a function that imitates the standard replicate function in Haskell, but using recursion. For example,

Prelude> replicate 3 "Ha!"
["Ha!","Ha!","Ha!"]

It should be of type Int -> a -> [a]. So far I have:

myReplicate :: Int -> a -> [a]
myReplicate x y = y : myReplicate (x-1) y
myReplicate 0 y = [ ]

However, my function always generates infinite lists:

Prelude> myReplicate 3 "Ha!"
["Ha!","Ha!","Ha!","Ha!","Ha!","Ha!","Ha!",...

Answer 1

You have to put the second case before the first, else it will never get to the second case.

myReplicate :: Int -> a -> [a]
myReplicate 0 y = [ ]
myReplicate x y = y : myReplicate (x-1) y

Answer 2

Your code should generate a warning reading (in GHC, at least):

Pattern match(es) are overlapped
In an equation for 'myReplicate': myReplicate 0 y = ...

What is happening is that the code tries to match your input against each definition you've written, in the order you've written (top-down). When you write f x = ..., the x variable will always match with any value of the type it represents. If all the bindings in the definition match, then that definition will be used.

In your case, the first definition is myReplicate x y = y : myReplicate (x-1) y. As I said, x and y will match with any value you pass, including 0 for the x binding. The solution proposed by @Alec shows how you can avoid this problem, by having the most specific pattern written first, and the catch-all pattern written last.

Another solution is using guards:

myReplicate :: Int -> a -> [a]
myReplicate x y
    | x > 0  = y : myReplicate (x-1) y
    | x == 0 = []
    | otherwise = [] -- or throw an exception, or use Maybe

This way you can write the expressions to be used in any order, if you write the conditions properly (in another words, if the conditions are mutually exclusive). Note the conditions will still be evaluated first from the top, then going down until a condition is true, pretty much like an if ... else if ... else if ... else ... chain in an imperative language.

Answer 3

You can use map:

myReplicate :: Int -> a -> [a]
myReplicate n x = map (const x) [1..n]

You can also use $> from Data.Functor:

import Data.Functor 
myReplicate :: Int -> a -> [a]
myReplicate n x = [1..n] $> x