[Haskell-cafe] Is this haskelly enough?

[Eric Mertens]

On 7/17/07, James Hunt <james at j-hunt.co.uk> wrote:
> As a struggling newbie, I've started to try various exercises in order
> to improve. I decided to try the latest Ruby Quiz
> (http://www.rubyquiz.com/quiz131.html) in Haskell. Would someone be kind
> enough to cast their eye over my code? I get the feeling there's a
> better way of doing it!
>
> subarrays :: [a] -> [[a]]
> subarrays [] = [[]]
> subarrays xs = (sa xs) ++ subarrays (tail xs)
>   where sa xs = [ys | n <- [1..length xs], ys <- [(take n xs)]]

Check out the functions in Data.List
inits :: [a] -> [[a]]
tails :: [a] -> [[a]]

also, in a list comprehension, rather than: ys <- [x] consider: let ys = x
in this specific case: [take n xs | n <- [1..length xs]] would be even better
(though using inits and tails to accomplish this would be best of all)

> maxsubarrays :: [Integer] -> [Integer]
> maxsubarrays xs = msa [] (subarrays xs)
>   where
>     msa m [] = m
>     msa m (x:xs)
>       | sum x > sum m = msa x xs
>       | otherwise     = msa m xs
>
> --for testing: should return [2, 5, -1, 3]
> main = maxsubarrays [-1, 2, 5, -1, 3, -2, 1]

This problem lends itself to being solved with Dynamic Programming and
can be solved in a single pass of the input list. (Rather than supply
the answer I'll encourage you to seek it out)