CODEWITHSUNDEEP
haskellfunctional-programming
mathandtic
mathandtic

Reputation: 159

Splitting lists in Haskell

In Haskell I need to perform a function, whose declaration of types is as follows:

split ::[Integer] -> Maybe ([Integer],[Integer])

Let it work as follows:

split [1,2,3,4,5,15] = Just ([1,2,3,4,5],[15])

Because, 1 + 2 + 3 + 4 + 5 = 15

split [1,3,3,4,3] = Just ([1,3,3],[4,3])

Because, 1 + 3 + 3 = 7 = 4 + 3

split [1,5,7,8,0] = Nothing

I have tried this, but it doesn't work:

split :: [Integer] -> ([Integer], [Integer])
split xs = (ys, zs)
 where
   ys <- subsequences xs,  ys isInfixOf xs, sum ys == sum zs
   zs == xs \\ ys

Determines whether the list of positive integers xs can be divided into two parts (without rearranging its elements) with the same sum. If possible, its value is the pair formed by the two parts. If it's not, its value is Nothing. How can I do it?

Upvotes: 0

Views: 1042

Answers (2)

RoadRunner
RoadRunner

Reputation: 26335

What you could also do is create a function that gives all possible splittings of a list:

splits :: [a] -> [([a], [a])]
splits xs = zipWith splitAt [1..(length xs)-1] $ repeat xs

Which works as follows:

*Main> splits [1,2,3,4,5,15]
[([1],[2,3,4,5,15]),([1,2],[3,4,5,15]),([1,2,3],[4,5,15]),([1,2,3,4],[5,15]),([1,2,3,4,5],[15])]

Then you could just use find from Data.List to find the first pair of splitted lists that have equal sums:

import Data.List

splitSum :: [Integer] -> Maybe ([Integer], [Integer])
splitSum xs = find (\(x, y) -> sum x == sum y) $ splits xs

Which works as intended:

*Main> splitSum [1,2,3,4,5,15]
Just ([1,2,3,4,5],[15])

Since find returns Maybe a, the types automatically match up.

Upvotes: 1

Davislor
Davislor

Reputation: 15164

Not a complete answer, since this is a learning exercise and you want hints, but if you want to use subsequences from Data.List, you could then remove each element of the subsequence you are checking from the original list with \\, to get the difference, and compare the sums. You were on the right track, but you need to either find the first subsequence that works and return Just (ys, zs), or else Nothing.

You can make the test for some given subsequence a predicate and search with find.

Upvotes: 3

Related Questions