CODEWITHSUNDEEP
listhaskell
Martin Thoma
Martin Thoma

Reputation: 136197

Haskell list comprehension - list of all list splits

I've just wanted to write a function splits that takes a list l and returns a list of tuples that contain all possible ways to split l.

So it should work like this:

splits "Hello"
[("","Hello"),("H","ello"),("He","llo"),("Hel","lo"),("Hell","o"),("Hello","")]

Implementation 1 What I wrote is this:

splits l = [(x,y) | i <- [0 ..length l], x <- take i l, y <- drop i l]

which gives

[('H','e'),('H','l'),('H','l'),('H','o'),('H','l'),('H','l'),('H','o'),
 ('e','l'),('e','l'),('e','o'),
 ('H','l'),('H','o'),
 ('e','l'),('e','o'),
 ('l','l'),('l','o'),
 ('H','o'),('e','o'),('l','o'),('l','o')]

Implementation 2 The correct solution is

splits l = [(take i l, drop i l) | i <- [0 ..length l]]

Question: Why are implementation 1 and implementation 2 doing different things? What's going on in implementation 1?

Upvotes: 3

Views: 951

Answers (1)

epsilonhalbe
epsilonhalbe

Reputation: 15967

The key observation is what the statement x <- list does in the first version. Let us look at a bit different example

[i | i <-[1..3]] => [1,2,3]

since String = [Char] one has

[c | c <- "Word"] => "Word" or equivalently ['W','o','r','d']

so we could correct your first version a teensy tiny bit and get the latter

splits l = [(x,y) | i <- [0 ..length l], x <- [take i l], y <- [drop i l]]

but still I have to say this is rather unidiomatic and a better solution in my eyes would be using a recursive function.

splits :: [a] -> [([a],[a])]
splits xx = splits' [] ([],xx)
  where splits' :: [([a],[a])]-> ([a],[a]) -> [([a],[a])]
        splits' acc xs@(_,[]) = reverse (xs:acc)
        splits' acc (xs,y:ys) = let xs' = (xs++[y],ys)
                                in splits' (xs':acc) xs'

or with higher order functions

splits :: [a] -> [([a],[a])]
splits xx = zipWith splitAt [0..(length xx)] (repeat xx)

Upvotes: 5

Related Questions