CODEWITHSUNDEEP
haskellrecursion
Leo Zhang
Leo Zhang

Reputation: 3230

How to pick elements in even index and odd index?

I have a list, I want to break the list into two, one with elements in the even indexes, and the other from the odd indexes.

breakByIndexes :: [a] -> ([a], [a])

For example:

> breakByIndexes ["A", "B", "C", "D"]
(["A", "C"], ["B", "D"]

> breakByIndexes ["A", "B", "C", "D", "E"]
(["A", "C", "E"], ["B", "D"]

I got a solution like this

breakByIndexes [] = ([], [])
breakByIndexes [e] = ([e], [])
breakByIndexes (e:o:xs) =
  let (es, os) = breakByIndexes xs
   in (e : es, o : os)

But I'm curious is it possible to implement without using recursion? And is it possible to implement by composing existing functions from Data.List?

Upvotes: 7

Views: 3980

Answers (5)

fp_mora
fp_mora

Reputation: 714

Just remember that ASCII characters have a built in index offset by 65.

import Data.Char (ord)

ord 'A' - 65 = 0`

Without the offset, the numeric values are even and odd anyway. 'A' is 65, odd.

p l = [ [x|x<-l,odd (ord(head x))], [x|x<-l,even (ord(head x))] ]

I do love pairs. Once a data set is in pairs it becomes much easier to work with. I came across a function that creates the perfect pairs for this set, it leaves unpaired elements at the end but in the list. It does not create tuples but list pairs are okay, too. The function is chunksOf.

Here it is used as

i3 = chunksOf 2 $ words "A B C D E F G H I"

To produce the pairs we want. [["A","B"],["C","D"],["E","F"],["G","H"],["I"]]

Pairs are even-odd pairs. The odd one at the end is really lacking an odd member. All odd elements of the list are missing the odd member. The odd member extractor has to compensate with filter of pairs with less than two members.

[ map (head) l3,   map (last) (filter ((>1).length) l3) ]

Produces [["A","C","E","G","I"],["B","D","F","H"]] Pairs carry information, such as even or odd.

And to my shock and awe @DanielWagner points out that transpose produces the desired results with the pair list. His is transpose i3 for an incredibly even more concise solution. Wow!

Edit 4/15/2018

I do hope this is final or near final.

let ls = words "A B C D E F G"
[[a|(a,b)<-zip ls [0..],bl b]|bl<-[even,odd]]

[["A","C","E","G"],["B","D","F"]]

Upvotes: 0

jferard
jferard

Reputation: 8180

EDIT: Since @DanielWagner opened the door, if it's possible to return a list instead of a tuple, an obvious solution is:

[[x | (x,i)<-zip xs [0..], i `mod` 2 == j] | j<-[0..1]]

It may be generalized to:

[[x | (x,i)<-zip xs [0..], i `mod` k == j] | j<-[0..k-1]]

For k lists of elements [[e_0, e_k, e_2k, ...], [e_1, e_k+1, e_2k+1, ...], ..., [e_k-1, e_2k-1, e_3k-1,...]].

For tuples, I leave for the record the previous code, though it's clearly worse than the other answers.

It's easy to pick even elements with a list comprehension:

Prelude> evens xs = [x | (x,i) <- zip xs [0..], even i]
Prelude> evens ["A", "B", "C", "D", "E"]
["A","C","E"]

You can do the same with odd elements. But you can also define a function that takes a filter (even or odd) and returns a function that will select elements:

Prelude> toFilter xs = \f -> [x | (x,i) <- zip xs [0..], f i]
Prelude> :t toFilter ["A", "B", "C", "D", "E"]
toFilter ["A", "B", "C", "D", "E"]
  :: (Num t, Enum t) => (t -> Bool) -> [[Char]]

toFilter xs takes a filter and returns a list:

Prelude> l = toFilter ["A", "B", "C", "D", "E"]
Prelude> l even
["A","C","E"]
Prelude> l odd
["B","D"]

It's also possible two define a function that takes a function like toFilter ((t -> Bool) -> [[Char]]) and create a tuple for even and odd filter:

Prelude> :t \tf -> (tf even, tf odd)
\tf -> (tf even, tf odd) :: Integral a => ((a -> Bool) -> t) -> (t, t)

Now, it becomes easy to put things together:

Prelude> breakByIndexes xs = (\tf -> (tf even, tf odd)) (\f -> [x | (x,i)<-zip xs [0..], f i])
Prelude> breakByIndexes ["A", "B", "C", "D"]
(["A","C"],["B","D"])
Prelude> breakByIndexes ["A", "B", "C", "D", "E"]
(["A","C","E"],["B","D"])

Less elegant than @elemx80s, but does the job...

Upvotes: 1

oisdk
oisdk

Reputation: 10091

My favourite version of this function uses foldr

pairs = foldr (\x ~(ys,zs) -> (x:zs,ys)) ([],[])

It works by swapping the tuple around on each item in the list. Inside the closure:

\x ~(odds,evens) -> (x:evens, odds)

You add on the x, which means that all of the rest of the elements in the evens list now become the odd-numbered elements.

What's the ~ for? It makes the pattern-match lazy. Without it, you'll force the tuple. So, for instance, if I wrote:

(head . fst . pairs) [1..]

It would not work without the ~. You could achieve the same effect by writing:

pairs = foldr (\x yszs -> (x:snd yszs,fst yszs)) ([],[])

Or:

pairs = foldr (\x -> uncurry (\ys zs -> (x:zs,ys))) ([],[])

Upvotes: 6

Daniel Wagner
Daniel Wagner

Reputation: 152837

Here is another way. Unlike the others answers at the time of posting, it naturally generalizes to other moduli than 2.

Data.List Data.List.Split> transpose . chunksOf 2 $ "ABCDE"
["ACE","BD"]

Upvotes: 5

Elmex80s
Elmex80s

Reputation: 3504

Yes you are right, using the partition function from Data.List. 

Prelude Data.List> (s, u) = partition (even . fst) (zip [0 .. ] "ABCD")
Prelude Data.List> (_, s2) = unzip s
Prelude Data.List> (_, u2) = unzip u
Prelude Data.List> (s2, u2)
("AC","BD")

How I found this? Go to Hoogle and fill in [a] -> ([a], [a]).

Upvotes: 8

Related Questions