Create sort of splitfunction haskell

Question

I want to split a list on 1 element and take the rest of the list in the second of the tuple and return that.

like this: *> split [1,2,3,2] gives [(1,[2,3,2]),(2,[1,3,2]),(3,[1,2,2]),(2,[1,2,3])]

I tried some code like this but it keeps giving me errors. Can someone help me out with this?

split :: [Int] -> [(Int,[Int])]
split [] = []
split (x:xs) = (map (x:) (map snd (split xs))) ++ [(x,[])]

Thx!

1. Always add the error you encounter. 2. You cannot map `(x:)` onto `[(Int, [Int])]`, since `(Int, [Int])` is not a list. 3. If you only use `xs` in the recursive call, you would always forget the start of the list. 4. Try to be more verbose. Write a function that, for a given index, splits the indexed value and the rest. Use this together with `zipWith [0..]` for a first prototype. — Zeta, Dec 23 '15 at 16:26

score 2 · Answer 1 · edited May 23 '17 at 12:31

My answer to an older question goes via an answer to this one.

I call this operation picks because it tells you all the ways to pick one out of a list (seen as a bag).

picks :: [x] -> [(x, [x])]
picks [] = []
picks (x : xs) = (x, xs) : [(y, x : ys) | (y, ys) <- picks xs]

It's standard issue zipper-wrangling kit, about which I've written at great length in other answers, such as the one linked above, and this one, for the works.

score 1 · Answer 2 · answered Dec 23 '15 at 17:08

1

This is possible with a list comprehension. Using zip you can create a tuple with an index and each element, then you can consturct a new tuple with your element and the original list minus the element at that index

splitter :: [a] -> [(a, [a])]
splitter xs = [(x, removeN n xs) | (n, x) <- zip [0..] xs]

That's using a function to remove the nth element

removeN :: Int -> [a] -> [a]
removeN n xs = take n xs ++ drop (n + 1) xs

example

*Main> splitter [1..4]
[(1,[2,3,4]),(2,[1,3,4]),(3,[1,2,4]),(4,[1,2,3])]

answered Dec 23 '15 at 17:08

Hamish

1,015
9
20

1

nice but this has quadratic complexity because of take/drop on each iteration – max taldykin Dec 23 '15 at 17:31
1

@maxtaldykin, that actually can't be avoided. The "pre-hole" parts of the result lists can't share any structure with each other. – dfeuer Dec 24 '15 at 02:59
However, using `splitAt` should give better constant factors. – dfeuer Dec 24 '15 at 06:30

max taldykin · Accepted Answer · 2015-12-24T09:30:24.310

1

You can use inits and tails from Data.List:

{-# LANGUAGE ParallelListComp #-}
split xs = [(x, pre ++ post) | pre <- inits xs | x:post <- tails xs]

or, if you don't like ParallelListComp:

split xs = [(x, pre ++ post) | (pre, x:post) <- zip (inits xs) (tails xs)]

edited Dec 24 '15 at 09:30

answered Dec 23 '15 at 17:28

max taldykin

12,459
5
45
64

Create sort of splitfunction haskell

3 Answers3