I'm returning to the Haskell community after a long absence. More on
that later. In working through the Real World Haskell book, I finally
hit [an
exercise](http://book.realworldhaskell.org/read/functional-
programming.html) that I found hard:
> -- Write a function splitWith that acts similarly to words,
> -- but takes a predicate and a list of any type,
> -- and splits its input list on every element for which the predicate returns False.
> -- my amendment. split on the ones on which it returns True
I'm not sure what made this hard, but I decided to first all specify
the type of the function, just to get going:
`splitWith :: (a -> Bool) -> [a] -> [[a]]`
I then decided on what had to happen with the most trivial case
`splitWith p [] = []`
Letting types drive your code
-----------------------------
At this point, I decided to write out the complex case in the most
general top-down fashion that I could, *respecting the type
signature*
`splitWith p xs = y'' : ys`
Now, I know that does not seem like a lot of code, but it basically is
how the data must flow through the functions, right? I mean how else
is a function that takes a predicate and a list going to return a list
of lists.
The beauty of Haskell is that I can derive y'' and ys via a set of
expressions, which is exactly what I did
Letting tests drive your code
-----------------------------
I wrote out some test cases and expected behavior:
-- splitWith odd [ 2,4,1,6,6,1,8,8] -- testCaseA
-- splitWith odd [1,2,4,1,6,6,1,8,8] -- testCaseB
-- splitWith odd [1,2,4,1,6,6,1,1,1,8,8] -- testCaseB2
-- splitWith odd [1,2,4,1,6,6,1,8,8,1] -- testCaseC
-- [ [2,4], [6,6], [8,8] ]
and then I began to figure out how to get y'' and ys to honor them
testCaseB is interesting. It is saying that you have to trim away
leading things obeying the predicate. So my first translation of the
input list (xs) did that:
splitWith p xs = y'' : ys
where y' = dropWhile p xs
And then I used break to get y'' and ys
splitWith p xs = y'' : ys
where y' = dropWhile p xs
(y'', rest) = break p y'
ys = splitWith p rest
edge case fails!
----------------
Now, the above function works well for everything except testCaseC,
where it leaves a blank list at the end of the result.
I realized that was happening when a list with a single element was
passed to the expression
`(y'', rest) = break p y'`
And wrote another function to address that case:
splitWith :: (a -> Bool) -> [a] -> [[a]]
splitWith p [] = []
splitWith p [x]
| p x = []
| otherwise = [[x]]
splitWith p xs = y'' : ys
where y' = dropWhile p xs
(y'', rest) = break p y'
ys = splitWith p rest
Conclusion
----------
I'm sure a Haskell expert could write this code in a much more concise
manner, and I'm sure I will too over time. But for right now, I need
to take baby steps and continue to develop problem-solving techniques,
such as the test and type-driven development I have discussed here.
|
