Simple list concatenating function (intersperse) in Haskell

June 25, 2023

I Am Very New To Haskell.

I’m trying to write an intersperse function that takes a list of lists of a e.g. a list of Strings, and one single a e.g. a char as a separator and returns a list of a or a String.

For example, if I call

intersperse ',' ["a", "b"]
-- I will get "a,b"

intersperse ',' ["hello"]
-- I will get only "hello"

intersperse ',' ["a", "b", "c"]
-- I will get "a,b,c"

intersperse 1 [[2,3,4], [5,6,7]]
-- I will get [2, 3, 4, 1, 5, 6, 7]

intersperse 1 [[2,3], [4,5], [6,7]]
-- I will get [2, 3, 1, 4, 5, 1, 6, 7]
--

So I wrote it as follows and it works fine.

intersperse :: a -> [[a]] -> [a]
intersperse s [] = []
intersperse s (x:[]) = x
intersperse s (x:xs) = loop x xs
  where loop a [] = a
        loop a (x:xs) = loop (a ++ [s] ++ x) xs

But if I add type signature to the loop function it will not compile, and I can’t realise what’s wrong

intersperse :: a -> [[a]] -> [a]
intersperse s [] = []
intersperse s (x:[]) = x
intersperse s (x:xs) = loop x xs
  where loop :: [a] -> [[a]] -> [a]
        loop a [] = a
        loop a (x:xs) = loop (a ++ [s] ++ x) xs

EDIT:

Isn’t lazy evaluation the default behavior in Haskell? Or are you referring to tail recursion?

>Solution :

But if I add type signature to the loop function it will not compile, and I can’t realise what’s wrong.

That is because the a in the where clause is a different one than the one at the top level. You can enable the ScopedTypeVariables extension [ghc-doc] for this:

{-# LANGUAGE ScopedTypeVariables #-}

intersperse :: forall a. a -> [[a]] -> [a]
intersperse s [] = []
intersperse s (x : []) = x
intersperse s (x : xs) = loop x xs
  where
    loop :: [a] -> [[a]] -> [a]
    loop a [] = a
    loop a (x : xs) = loop (a ++ [s] ++ x) xs

The intersperse function is not written lazily however, this means that for large lists, it will take a lot of time before the result is handed to the caller, and will consume a lot of memory, and for infinite lists, it will get in an infinite loop that will end when memory is exhausted.

You can optimize the function with:

intersperse :: a -> [[a]] -> [a]
intersperse s [] = []
intersperse s [x] = x
intersperse s (x : xs) = x ++ go xs
  where
    go [] = []
    go (x : xs) = s : x ++ go xs