7

I'm trying to change a list in haskell to include 0 between every element. If we have initial list [1..20] then i would like to change it to [1,0,2,0,3..20]

What i thought about doing is actually using map on every function, extracting element then adding it to list and use ++[0] to it but not sure if this is the right approach or not. Still learning haskell so might have errors.

My code:

x = map classify[1..20] 

classify :: Int -> Int 
addingFunction 0 [Int]


addingFunction :: Int -> [a] -> [a]
addingFunction x xs = [a] ++ x ++ xs 

6 Answers 6

12

intersperse is made for this. Just import Data.List (intersperse), then intersperse 0 yourList.

1
  • Yes that works too but kinda wanted to dig deep to Understand Haskell more Oct 18, 2019 at 0:11
8

You cannot do this with map. One of the fundamental properties of map is that its output will always have exactly as many items as its input, because each output element corresponds to one input, and vice versa.

There is a related tool with the necessary power, though:

concatMap :: (a -> [b]) -> [a] -> [b]

This way, each input item can produce zero or more output items. You can use this to build the function you wanted:

between :: a -> [a] -> [a]
sep `between` xs = drop 1 . concatMap insert $ xs
  where insert x = [sep, x]

0 `between` [1..10]
[1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,10]

Or a more concise definition of between:

between sep = drop 1 . concatMap ((sep :) . pure)
4

With simple pattern matching it should be:

addingFunction n [] = []
addingFunction n [x] = [x]
addingFunction n (x:xs) = x: n : (addingFunction n xs)

addingFunction 0 [1..20]
=> [1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,10,0,11,0,12,0,13,0,14,0,15,0,16,0,17,0,18,0,19,0,20]
3

If you want to use map to solve this, you can do something like this:

Have a function that get a int and return 2 element list with int and zero:

addZero :: List
addZero a = [0, a]

Then you can call map with this function:

x = map addZero [1..20] -- this will return [[0,1], [0, 2] ...] 

You will notice that it is a nested list. That is just how map work. We need a way to combine the inner list together into just one list. This case we use foldl

combineList :: [[Int]] -> [Int]
combineList list = foldl' (++) [] list 
-- [] ++ [0, 1] ++ [0, 2] ... 

So the way foldl work in this case is that it accepts a combine function, initial value, and the list to combine.

Since we don't need the first 0 we can drop it:

dropFirst :: [Int] -> [Int]
dropFirst list = case list of
  x:xs -> xs
  [] -> []

Final code:

x = dropFirst $ combineList $ map addZero [1..20]

addZero :: Int -> [Int]
addZero a = [0, a]

combineList :: [[Int]] -> [Int]
combineList list = foldl (++) [] list 

dropFirst :: [Int] -> [Int]
dropFirst list = case list of
  x:xs -> xs
  [] -> []

4
  • 1
    foldl (++) [] is a bit weird. Why not just point to concat?
    – amalloy
    Oct 18, 2019 at 9:31
  • 1
    @amalloy Yes it is. It is just that concat implementation itself also use some type of fold. So I guess using foldl would help other understand it a bit deeper.
    – Rinne Hmm
    Oct 18, 2019 at 10:06
  • 1
    concat is implemented using foldr rather than foldl. Do you understand why this is actually important?
    – dfeuer
    Oct 18, 2019 at 17:57
  • I do not fully understand the subject of foldmyself. There is a whole wiki related to this subject. My simple understanding is that foldr is much better for lazy infinite list, and foldl or foldl' (strict version) is better for general use-case.
    – Rinne Hmm
    Oct 20, 2019 at 6:58
2

We here can make use of a foldr pattern where for each element in the original list, we prepend it with an 0:

addZeros :: Num a => [a] -> [a]
addZeros [] = []
addZeros (x:xs) = x : foldr (((0 :) .) . (:)) [] xs
0
2

If you don't want to use intersperse, you can write your own.

intersperse :: a -> [a] -> [a]
intersperse p as = drop 1 [x | a <- as, x <- [p, a]]

If you like, you can use Applicative operations:

import Control.Applicative

intersperse :: a -> [a] -> [a]
intersperse p as = drop 1 $ as <**> [const p, id]

This is basically the definition used in Data.Sequence.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.