How is map implemented internally?

Question

Ok so i want to implement my custom map that receives a replication factor and a target list.

Inputs: Int -> [Int]
Output: [[Int]]
E.g.: 2 [1,2] -----> [[1,1],[2,2]]

f [1,2,3] -> map -> [f(1),f(2),f(3)]

What is supposed to happen with f(1) when map goes to the next element of the list?How should i replace 1 with f(1) ?

P.S: This was my initial solution but it does replicate the initial list,not every element.

replicate::Int->[Int]->[[Int]]
replicate 1 x=x
replicate factor (x:xs)= go factor [] (x:xs) where
                         go factor ls (x:xs) =go factor (repl factor x):ls xs 
                         repl 1 nr=nr
                         repl times nr=nr:repl (times-1) nr

Answer 1

custom map that receives a replication factor and a target list

It is a little unclear to me what you're asking for.

Does mymap receive the replication factor, or does f?

E.g.: 2 [1,2] -----> [[1,1],[2,2]]

If you want mymap 2 [1,2] to give [[1,1],[2,2]], then:

mymap :: Int -> [a] -> [[a]]
mymap = map . replicate

However,

mymap :: (Int -> [Int]) -> [Int] -> [[Int]]

How is this function any different from the built-in map :: (a -> b) -> [a] -> [b] with a as Int and b as [Int]? Here, mymap does not have any Int argument itself, so you must mean that f's argument is the replication factor; but if f 2 3 == [3,3], then f is replicate and you can use the solution above.

You can write this using your own recursive definitions, if you like:

mymap :: Int -> [a] -> [[a]]
mymap _ [] = []
mymap n (x:xs) = myreplicate n x : mymap n xs

myreplicate :: Int -> a -> [a]
myreplicate 0 _ = []
myreplicate n x = x : myreplicate (n-1) x

Or you can use list comprehension instead of a map:

mymap :: Int -> [a] -> [[a]]
mymap n xs = [ replicate n x | x <- xs ]

I'd probably call mymap for replicateMany or something like that.

Answer 2

There are two issues, that prevent your code from compiling:

1. null function has the type [a0] -> Bool, but you're applying it on an element of a list, hence you're expecting it to be Int -> Bool

2. The result f x shouldn't be pushed into the tail of the input, it should be pushed into the result of recursive call of the function: f x: (mymap f xs) instead of f x: xs

As a result the following code should work:

mymap :: (Int -> [Int]) -> [Int]-> [[Int]]
mymap f (x:xs) = if null xs then [] else f x : (mymap f xs)

By the way, the Standard Library provides much readable (and also polymorphic) implementation using pattern-matching:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs