https://twitter.com/1HaskellADay/status/480968262516506625

haskell_a_day_2014_06_23.hs

module MatchingSub where

import Data.List

-- | Submit these to MissingH
dropWhilePrefixList :: ([a] -> Bool) -> [a] -> [a]
dropWhilePrefixList = go []
  where go :: [a] -> ([a] -> Bool) -> [a] -> [a]
        go _ _ [] = []
        go acc p rest@(x : xs) = if (not . p) acc then rest else go (acc ++ [x]) p xs

takeWhilePrefixList :: ([a] -> Bool) -> [a] -> [a]
takeWhilePrefixList = go []
  where go :: [a] -> ([a] -> Bool) -> [a] -> [a]
        go acc _ [] = acc
        go acc p (x : xs) = if (not . p) acc then acc else go (acc ++ [x]) p xs

spanPrefixList :: ([a] -> Bool) -> [a] -> ([a], [a])
spanPrefixList p xs = (takeWhilePrefixList p xs, dropWhilePrefixList p xs)

-- | List the sub-sequences of conscutives elements in the list such that the
-- sum of the element is equal to the given number.
--
-- Examples:
--
-- >>> matchingSequential 10 [1..5]
-- [[1,2,3,4]]
--
-- >>> matchingSequential 2 $ replicate 3 1
-- [[1,1]]
--
-- >>> take 2 $ matchingSequential 2 $ repeat 1
-- [[1,1],[1,1]]
matchingSequential :: Int -> [Int] -> [[Int]]
matchingSequential n xs =
  let (sub, rest) = spanPrefixList (\ys -> sum ys /= n) xs
  in case sub of
       [] -> [rest | sum rest == n]
       _ -> (if sum sub == n then (sub :) else id) (matchingSequential n rest)

continuousSubsequences :: [a] -> [[a]]
continuousSubsequences xs = [] : (filter (not . null) . concatMap tails $ inits xs)

-- | List the sub-sequences of conscutives elements in the list such that the
-- sum of the element is equal to the given number.
--
-- Examples:
--
-- >>> matchingSub 10 [1..5]
-- [[1,2,3,4]]
--
-- >>> matchingSub 2 $ replicate 3 1
-- [[1,1],[1,1]]
--
-- >>> take 2 $ matchingSub 2 $ repeat 1
-- [[1,1],[1,1]]
matchingSub :: Int -> [Int] -> [[Int]]
matchingSub n xs = filter (\ys -> sum ys == n) (continuousSubsequences xs)