[Haskell-cafe] a sort of chunk

[Viktor Dukhovni]

On Fri, Jan 17, 2020 at 05:41:12PM -0500, Viktor Dukhovni wrote:

> To your specific question I would refactor this a bit:
> 
>     -- | Split a list after the first element that reaches a target cumulative weight
>     --
>     splitWeight :: Int -> (a -> Int) -> [a] -> ([a], [a])
>     splitWeight target weight xs =
>         (,) <$> reverse . fst <*> snd $ go 0 xs []
>       where 
>         go _ [] acc = (acc, [])
>         go n (h:ts) acc
>             | let w = n + weight h
>             , w < target    = go w ts $ h : acc
>             | otherwise     = (h : acc, ts)

An alternative implementation of splitWeight is lazier, and produces the
first element of the initial chunk in constant time even when the target
weight is large and requires billions of elements (on a 64bit system):

    -- import Data.Bifunctor

    splitWeight' :: Int -> (a -> Int) -> [a] -> ([a], [a])
    splitWeight' target weight xs = go 0 xs
      where
        go _ [] = ([], [])
        go n (h:ts)
            | let w = n + weight h
            , w < target    = first (h:) $ go w ts
            | otherwise     = ([h], ts)

        -- Define directly, or import from Data.Bifunctor
        first f ~(a, b) = (f a, b)

λ> take 5  $ fst $ splitWeight' (maxBound :: Int) id [1..]
[1,2,3,4,5]

-- 
    Viktor.