Difference between revisions of "99 questions/Solutions/17"
Amackillop (talk | contribs) (Added a solution.) |
|||
(8 intermediate revisions by 7 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> |
||
+ | Or even simpler using <hask>splitAt</hask>: |
||
⚫ | |||
+ | |||
+ | <haskell> |
||
+ | split = flip splitAt |
||
+ | </haskell> |
||
+ | |||
⚫ | |||
+ | |||
<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]) |
||
− | split xs 0 = ( |
+ | split (x:xs) n | n > 0 = let (f,l) = split xs (n-1) in (x : f, l) |
− | split |
+ | split xs _ = ([], xs) |
+ | </haskell> |
||
+ | |||
+ | Or (ab)using the "&&&" arrow operator for tuples: |
||
+ | |||
+ | <haskell> |
||
+ | split :: [a] -> Int -> ([a], [a]) |
||
+ | split (x:xs) n | n > 0 = (:) x . fst &&& snd $ split xs (n - 1) |
||
+ | split xs _ = ([], xs) |
||
+ | </haskell> |
||
+ | |||
+ | 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> |
||
+ | |||
+ | A solution that dequeues onto a stack and then reverses at the end: |
||
+ | <haskell> |
||
+ | split :: [a] -> Int -> ([a], [a]) |
||
+ | split xs n = let (a, b) = helper [] xs n in (reverse a, b) |
||
+ | where helper left right@(r:rs) n |
||
+ | | n == 0 = (left, right) |
||
+ | | otherwise = helper (r:left) rs (n - 1) |
||
+ | |||
+ | </haskell> |
||
+ | |||
+ | --- |
||
+ | |||
+ | A recursive solution constructing the 2-tuple: |
||
+ | |||
+ | <haskell> |
||
+ | split :: [a] -> Int -> ([a],[a]) |
||
+ | |||
+ | split [] _ = ([],[]) |
||
+ | |||
+ | split (x:xs) n |
||
+ | | n > 0 = ( |
||
+ | x: (fst (split xs (n-1))), |
||
+ | snd (split xs (n-1)) |
||
+ | ) |
||
+ | | n <= 0 = ( |
||
+ | fst (split xs 0), |
||
+ | x:(snd (split xs 0)) |
||
+ | ) |
||
+ | </haskell> |
||
+ | |||
+ | A simple solution using recursion: |
||
+ | <haskell> |
||
+ | splitAt3 :: Int -> [a] -> ([a], [a]) |
||
+ | splitAt3 n xs = if n < 0 then ([], xs) else splitR n xs [] |
||
+ | where |
||
+ | splitR 0 xs accum = (reverse accum, xs) |
||
+ | splitR _ [] accum = (reverse accum, []) |
||
+ | splitR n (x:xs) accum = splitR (n-1) xs (x : accum) |
||
</haskell> |
</haskell> |
||
+ | [[Category:Programming exercise spoilers]] |
||
− | Note that this function, with the parameters in the other order, exists as <hask>splitAt</hask>. |
Latest revision as of 21:07, 10 March 2019
(*) 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 (x:xs) n | n > 0 = let (f,l) = split xs (n-1) in (x : f, l)
split xs _ = ([], xs)
Or (ab)using the "&&&" arrow operator for tuples:
split :: [a] -> Int -> ([a], [a])
split (x:xs) n | n > 0 = (:) x . fst &&& snd $ split xs (n - 1)
split xs _ = ([], xs)
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))
A solution that dequeues onto a stack and then reverses at the end:
split :: [a] -> Int -> ([a], [a])
split xs n = let (a, b) = helper [] xs n in (reverse a, b)
where helper left right@(r:rs) n
| n == 0 = (left, right)
| otherwise = helper (r:left) rs (n - 1)
---
A recursive solution constructing the 2-tuple:
split :: [a] -> Int -> ([a],[a])
split [] _ = ([],[])
split (x:xs) n
| n > 0 = (
x: (fst (split xs (n-1))),
snd (split xs (n-1))
)
| n <= 0 = (
fst (split xs 0),
x:(snd (split xs 0))
)
A simple solution using recursion:
splitAt3 :: Int -> [a] -> ([a], [a])
splitAt3 n xs = if n < 0 then ([], xs) else splitR n xs []
where
splitR 0 xs accum = (reverse accum, xs)
splitR _ [] accum = (reverse accum, [])
splitR n (x:xs) accum = splitR (n-1) xs (x : accum)