On 7/17/07, James Hunt
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)