[Haskell-cafe] Is this haskelly enough? -- errm but every answer is wrong(?)

[Albert Y. C. Lai]

Anthony Clayden wrote:
> (Or at least the problem is under-specified.)
> 
> 1. There may be several sub-sequences having the maximum
> sum.
>    So the type for the solution should be :: Num a => [a] ->
> [[a]]

> 2. The inits . tails approach adds a fault:
>    It introduces a sprinkling of empty sub-sequences. These
> have sum zero.
>    So in case the input list is all negative numbers ...
> 
> Being a software tester for my day job, I looked first not
> for an elegant and/or efficient solution; but for where to
> stretch the boundaries of the problem.

I am an academic into formal methods. Contrary to common myth, my 
perspective is compatible with, not contrary to, the tester perspective. 
If you start from testing and let one of your "size" or "coverage" 
parameters tend to infinity, you arrive at a formal method. Both 
perspectives demand well-scoped specifications, otherwise there is 
little to test for or verify against. Thus, I also look first for 
boundaries of problems.

Here are two test cases:

(A) [2, -10, 2]

(B) [-10, -11]

Following point #1, the answer to (A) may be [[2]] or [[2], [2]], 
depending on whether you consider the first [2] to be "the same as" the 
second [2]. Some people say, "[2]==[2], they are the same". Some other 
people say, "they occur at different places, they are different, in fact 
it is probably more interesting to give indexes rather than list 
contents, e.g., [(0,0), (2,2)]".

If you decide they are the same, then I have little to say about (B) and 
point #2, except that you should beware that the answer to (B) is [[]], 
and in your effort of killing off empty lists you should be careful in 
preserving one of them.

If you decide they are different, then point #2 is ill advice. As you 
would consider multiple occurrences of [2] to be distinct because they 
come from different positions, so you would consider multiple occurences 
of [] to be distinct because they come from different positions. In (B), 
there are three occurrences of []: before -10, between -10 and -11, and 
after -11. All three should be reported as answers. The answer should be 
[[], [], []] or [(0,-1), (1,0), (2,1)]. It is in fact paramount to use 
inits . tails or equivalent to sprinkle empty subsequences, since that's 
the only way you won't miss them.