CODEWITHSUNDEEP
haskell
Kemal
Kemal

Reputation: 115

Halving a list into sublists using pattern matching

I am trying to get the output, given an input

> halve [1,2,3,4,5,6]
([1,2,3],[4,5,6])

I have solved this problem using this approach: 

halve xs = ((take s xs), (drop s xs))
    where
      s = (length xs) `div` 2

I am a beginner in Haskell and I want to learn how to solve this question using pattern matching? Thanks

Upvotes: 1

Views: 220

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477160

You can make use of a variant of the hare and tortoise algorithm. This algorithm basically runs over the list with two iterators: the hare taking two hops at a time, and the tortoise performing one hop at that time.

When the hare reaches the end of the list, then we know that the tortoise is halfway, and thus can split the list in half: the list seen thus far is the first half, and the list still to enumerate over, is the second half.

An algorithm thus looks like:

half :: [a] -> ([a], [a])
half h = go h h
    where go (_:(_:hs)) (t:ts) = (..., ...)
              where (a, b) = go ...
          go _ (t:ts) = (..., ...)
          go _ [] = (..., ...)

with the ... parts still to fill in.

Upvotes: 5

Related Questions