CODEWITHSUNDEEP
listhaskellfold
Cat
Cat

Reputation: 1363

Haskell - separate a list of pairs in two lists using fold

So, I am given a list containing tuples and I need to break it down into two lists, the first list containing the elements with odd index and the second list containing the elements with even index, must be done using fold, here is my attempt:

breakList :: [(Integer, Integer)] -> [[(Integer, Integer)]]
breakList [] = [[], []]
breakList xxs@(x:xs) = foldl (\ acc y -> if length (acc !! 0) < length (acc !! 1) then y : (acc !! 0) else y : (acc !! 1)  )  [[], []] xxs

Error I am getting:

Couldn't match type '(Integer, Integer)' with '[(Integer, Integer)]' Expected type: [[(Integer, Integer)]]

when hovering over y : (acc !! 1) and y : (acc !! 0)

Example:

Input:

ex1 = [ (2, 2), (1, 3), (2, 3), (2, 4), (3, 5), (0, 2), (2, 1), (1, 4) , (2, 0), (1, 2), (3, 1), (1, 0)]

Output

breakList ex1 == ( [(2,2),(2,3),(3,5),(2,1),(2,0),(3,1)] , [(1,3),(2,4),(0,2),(1,4),(1,2),(1,0)])

Upvotes: 1

Views: 1682

Answers (2)

Will Ness
Will Ness

Reputation: 71065

The standard trick here, as hinted at by Willem in the comments, which I first saw few years back on SO in an (F# or Ocaml) answer by [user:Ed'ka], is

evenodds :: [a] -> ([a], [a])
evenodds xs = foldr g ([],[]) xs
  where
  g x ~(as,bs) = (bs,x:as)

or

oddevens :: [a] -> ([a], [a])
oddevens xs = foldr g ([],[]) xs
  where
  g x ~(bs,as) = (x:as,bs)

What are odd positions from here, are even positions from the position one notch further on the list.

The tilde ~ introduces a lazy pattern so that the function is properly lazy in its operations.

Upvotes: 2

assembly.jc
assembly.jc

Reputation: 2066

Note that you want to split a list into two lists of a pair, so the return type should be

([(Integer, Integer)], [(Integer, Integer)])

not

[[(Integer, Integer)]]

and access the element of pair, you can use fst and snd instead of through index, and finally, use foldl will return the resulted list in reversed order, it can be fixed use foldr instead. The correction look like:

breakList :: [(Integer, Integer)]->([(Integer, Integer)], [(Integer, Integer)])
breakList xxs = foldr (\y acc-> if length (fst acc) < length (snd acc)
                                then (y:(fst acc), snd acc)
                                else (fst acc, y:(snd acc)) ) ([], []) xxs

Upvotes: 1

Related Questions