Home / Questions / 29648
Accepted
Ramosaurio
Asked: 2020-10-25 23:45:07 +0800 CST 2020-10-25 23:45:07 +0800 CST

Parcel List into Tuple of Lists (Haskell)

  • 772

We have the following function:

repartir [a] -> ([a],[a])

So partition should partition the main list into two lists by taking the elements like this:

repartir [1,2,3,4,5]

---> ([1,3,5],[2,4])

repartir "hola"

---> ("hl","oa")

We can only import:import Data.List

Greetings and thank you

haskell

3 Answers

  1. A more efficient solution, without using module functions Data.Listand going through the list only once, could be this:

    repartir :: [a] -> ([a],[a])
repartir = repartir' True

repartir' :: Bool -> [a] -> ([a],[a])
repartir' _ [] = ([],[])
repartir' g (x:xs) = let (a,b) = repartir' (not g) xs in if g then (x:a,b) else (a,x:b)
    • 2

  2. In these cases it is best to go step by step simplifying the problem.

    You can see the cast as two separate cases (the two elements of the tuple). The first takes two from the list discarding the second and the second from the tuple also takes two but discards the first.

    For the first:

    reparte1 :: [a] -> [a]                       -- firma
reparte1 (x:_:xs) = x : reparte1 xs          -- tomo el 1ro, descarto el 2do

    But...

    *Main> reparte1 "hola"
"hl*** Exception: Non-exhaustive patterns in function reparte1

    The obvious is missing, the closing case. Now it would be:

    reparte1 :: [a] -> [a]                       -- firma
reparte1 [] = []                             -- fin
reparte1 (x:_:xs) = x : reparte1 xs          -- tomo el 1ro, descarto el 2do

    Now fails on odd:

    *Main> reparte1 "hola"
"hl"
*Main> reparte1 "holas"
"hl*** Exception: Non-exhaustive patterns in function reparte1

    Easy to fix. You add this case:

    reparte1 :: [a] -> [a]                       -- firma
reparte1 [] = []                             -- fin
reparte1 [x] = [x]                           -- cuando quede uno me lo quedo
reparte1 (x:_:xs) = x : reparte1 xs          -- tomo el 1ro, descarto el 2do

*Main> reparte1 "hola"
"hl"
*Main> reparte1 "holas"
"hls"

    Case 2 is the same but you discard the first item and keep the second. With odd amount of elements you ignore it.

    reparte2 :: [a] -> [a]                       -- firma
reparte2 [] = []                             -- fin
reparte2 [x] = []                            -- cuando quede uno lo ignoro
reparte2 (_:x:xs) = x : reparte2 xs          -- descarto el 1ro, tomo el 2do

*Main> reparte2 "holas"
"oa"

    And finally you put the two cases together.

    repartir :: [a] -> ([a],[a])
repartir (x) = (reparte1 x, reparte2 x)

*Main> repartir [1,2,3,4,5]
([1,3,5],[2,4])
*Main> repartir "hola"
("hl","oa")

    Optimization is left to the student. ;-)

    • 1
  3. Best Answer

    A direct way:

    repartir :: [a] -> ([a],[a])
repartir xs = ([xs!!i | i <- [0,2..n]], [xs!!i | i <- [1,3..n]])
    where n = length xs - 1

    The operator !!is not very efficient on lists, so don't overuse it. A more efficient version:

    repartir :: [a] -> ([a],[a])
repartir xs = ([x | (i,x) <- zs, odd i], [x | (i,x) <- zs, even i])
    where zs = zip [1..] xs

    PS: It was not necessary to import the module Data.Listsince the necessary functions are included in thePrelude

    There is a better solution using types Either. The downside is that you need to import the module Data.Either:

    import Data.Either (partitionsEithers)

repartir :: [a] -> ([a],[a])
repartir = partitionEithers . zipWith id (cycle [Left,Right])
    • 1