[Haskell-cafe] Help with Bird problem 4.5.6: sequence of
successive maxima
Daniel Fischer
daniel.is.fischer at web.de
Sun Mar 15 16:52:57 EDT 2009
Am Sonntag, 15. März 2009 21:09 schrieb R J:
> This Bird problem vexes me, in the first instance because it doesn't seem
> to specify a unique solution:
>
> Given a list xs = [x_1, x_2, . . . , x_n], the sequence of successive
> maxima "ssm xs" is the longest subsequence [x_j1, x_j2, x_j3..x_jk] such
> that j_1 = 1 and j_m < j_n => x_jm < x_jn. For example, xs = [3, 1, 3, 4,
> 9, 2, 10, 7] => ssm xs = [3, 4, 9, 10]. Define "ssm" in terms of "foldl".
>
> From this specification, I infer:
>
> ssm [] = []
> ssm [1] = [1]
> ssm [1, 2, 3] = [1, 2, 3]
> ssm [1, 0, 3, 2] = [1, 3]
>
> However, what is ssm [1,0,100,2,3,4,5]? Is it [1, 100] or [1, 2, 3, 4, 5]?
> I think the latter, but am not certain.
Since [1,2,3,4,5] is longer than [1,100], it's the former.
But if we consider the example [1,0,3,2], the two lists [1,3] and [1,2] are
equally long, both are valid answers given the above spec.
So if you want one list as the answer, you have to add a criterium to choose.
> Whichever it is, what's the solution?
Is the above all that Bird gives as specification or was there more?
>
> Thanks.
>
More information about the Haskell-Cafe
mailing list