[Haskell-cafe] Help with Bird problem 4.5.6: sequence of successive maxima

[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.  Whichever it is, what's the solution?

Thanks.


_________________________________________________________________
Windows Live™ Groups: Create an online spot for your favorite groups to meet.
http://windowslive.com/online/groups?ocid=TXT_TAGLM_WL_groups_032009
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090315/183d1952/attachment.htm