Personal tools

99 questions/Solutions/17

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
 
m (added another fold solution)
(2 intermediate revisions by 2 users not shown)
Line 3: Line 3:
 
Do not use any predefined predicates.
 
Do not use any predefined predicates.
  
Solution using take and drop:
+
Solution using <hask>take</hask> and <hask>drop</hask>:
 +
 
 
<haskell>
 
<haskell>
 
split xs n = (take n xs, drop n xs)
 
split xs n = (take n xs, drop n xs)
 
</haskell>
 
</haskell>
  
Alternatively, we have the following recursive solution:
+
Or even simpler using <hask>splitAt</hask>:
 +
 
 +
<haskell>
 +
split = flip splitAt
 +
</haskell>
 +
 
 +
But these should clearly be considered "predefined predicates". Alternatively, we have the following recursive solution:
 +
 
 
<haskell>
 
<haskell>
 
split :: [a] -> Int -> ([a], [a])
 
split :: [a] -> Int -> ([a], [a])
Line 18: Line 26:
  
 
The same solution as above written more cleanly:
 
The same solution as above written more cleanly:
 +
 
<haskell>
 
<haskell>
 
split :: [a] -> Int -> ([a], [a])
 
split :: [a] -> Int -> ([a], [a])
Line 24: Line 33:
 
</haskell>
 
</haskell>
  
Note that this function, with the parameters in the other order, exists as <hask>splitAt</hask>.
+
A similar solution using foldl:
 +
 
 +
<haskell>
 +
split :: [a] -> Int -> ([a], [a])
 +
split [] _ = ([], [])
 +
split list n
 +
  | n < 0 = (list, [])
 +
  | otherwise  = (first output, second output)
 +
    where output = foldl (\acc e -> if third acc > 0 then (first acc ++ [e], second acc, third acc - 1) else (first acc, second acc ++ [e], third acc)) ([], [], n) list
 +
</haskell>
 +
 
 +
Note that for the above code to work you must define your own first, second, and third functions for tuples containing three elements like so:
 +
 
 +
<haskell>
 +
first :: (a, b, c) -> a 
 +
first (x, _, _) = x 
 +
 
 +
second :: (a, b, c) -> b 
 +
second (_, y, _) = y 
 +
 
 +
third :: (a, b, c) -> c 
 +
third (_, _, z) = z 
 +
</haskell>
 +
 
 +
Another foldl solution without defining tuple extractors:
 +
<haskell>
 +
split :: [a] -> Int -> ([a],[a])
 +
split lst n = snd $ foldl helper (0,([],[])) lst
 +
    where helper (i,(left,right)) x = if i >= n then (i+1,(left,right++[x])) else (i+1,(left++[x],right))
 +
</haskell>

Revision as of 00:31, 24 December 2011

(*) Split a list into two parts; the length of the first part is given.

Do not use any predefined predicates.

Solution using
take
and
drop
:
split xs n = (take n xs, drop n xs)
Or even simpler using
splitAt
:
split = flip splitAt

But these should clearly be considered "predefined predicates". Alternatively, we have the following recursive solution:

split :: [a] -> Int -> ([a], [a])
split []         _             = ([], [])
split l@(x : xs) n | n > 0     = (x : ys, zs)
                   | otherwise = ([], l)
    where (ys,zs) = split xs (n - 1)

The same solution as above written more cleanly:

split :: [a] -> Int -> ([a], [a])
split xs 0 = ([], xs)
split (x:xs) n = let (f,l) = split xs (n-1) in (x : f, l)

A similar solution using foldl:

split :: [a] -> Int -> ([a], [a])
split [] _ = ([], [])
split list n
  | n < 0 = (list, [])
  | otherwise  = (first output, second output)
    where output = foldl (\acc e -> if third acc > 0 then (first acc ++ [e], second acc, third acc - 1) else (first acc, second acc ++ [e], third acc)) ([], [], n) list

Note that for the above code to work you must define your own first, second, and third functions for tuples containing three elements like so:

first :: (a, b, c) -> a  
first (x, _, _) = x  
 
second :: (a, b, c) -> b  
second (_, y, _) = y  
 
third :: (a, b, c) -> c  
third (_, _, z) = z

Another foldl solution without defining tuple extractors:

split :: [a] -> Int -> ([a],[a])
split lst n = snd $ foldl helper (0,([],[])) lst
    where helper (i,(left,right)) x = if i >= n then (i+1,(left,right++[x])) else (i+1,(left++[x],right))