How do you solve this Haskell problem using a fold map and take?

Question

Define a function replicate which given a list of numbers returns a list with each number duplicated its value. Use a fold, map, and take

..> replicate [5,1,3,2,8,1,2]

output: [5,5,5,5,5,1,3,3,3,2,2,8,8,8,8,8,8,8,8,1,2,2]

I've figure this out using List comprehension and recursion:

replicate2 [] = []
replicate2 (n:nn) = take n(repeat n) ++ replicate2 nn

but how would you use fold and map to do this? so far I have: replicate n = map (foldl1 (take n(repeat n)) n) n which is obviously wrong, but I think I am close..

so any help would be nice, THANKS!

Answer 1

You've got your function application order mixed up. Think about what you need to be able to do:

1. Turn a number n into a list of n copies of itself
2. Apply operation #1 on every number in a list
3. Concatenate all the lists you got from #2 together.

You know how to do 1: take n $ repeat n
Of 2 and 3, which is a map and which is a fold?

Step 2. is a map - you're mapping ("transforming") every item in the list, into a list.
Step 3. is a fold, since you're aggregating ("flattening") a bunch of list elements into one.

Answer 2

The key in Haskell is always follow the types:

foldr  :: (a -> b -> b) -> b -> [a] -> b
foldr1 :: (a -> a -> a)      -> [a] -> a
map    :: (a -> b)           -> [a] -> [b]
take   :: Int                -> [a] -> [a]

I've added some spaces here to make it a bit more clear how these three functions compare. Remember when you look at these that a type variable, a or b, can match any type, including things like String, or [Float], or even [(String,[Int])]. For example, in the expression:

foldr (\a b -> product a + b) (0::Int) [[1,2,4],[5,2],[0,3,6]]

foldr is being used as type ([Int] -> Int -> Int) -> Int -> [[Int]] -> Int. That is a has matched [Int] and b has matched Int.

Now: Think about at the "outermost" level what your expression has to do. Which of these functions fits that form?

Can you cast your problem into an outer expression that has one of these forms and an "inner" problem?