SML: how to listify list to sublist

Viewed 1754

I found this question from CS 217.

Divide a list into one or more sublists so that each sublist contains integers in nondecreasing (sorted) order.

[3,5,1,8,9,2,1,0] returns [[3,5],[1,8,9],[2],[1],[0]]

[1,2,3,4,5,6] returns [[1,2,3,4,5,6]]

[5,4,3,2,1] returns [[5],[4],[3],[2],[1]]

below code works:

val Q1 = [ 3, 5, 1, 8, 9, 2, 1, 0 ]

val A1 = foldl (
    fn (x, a) => 
        if x > hd (hd a) then (x::hd a)::tl a
        else [x]::a 
    ) [ [ hd Q1 ] ] (tl Q1)

val A1 = map rev (rev A1)

or like this: use 2 temporary list to collect.

fun split l = let
    fun split' tmp subset =
        fn [] => []
        |  [x] => (x::tmp)::subset
        |  (a::(c as b::_)) =>
                if a < b then split' (a::tmp) subset c
                else split' [] ((a::tmp)::subset) c
    in (rev o map rev) (split' [] [] l) end

So many solutions for this question, But I still want to know how to code it as a pattern match function? maybe something like below:

(Not sure if it is possible?)

fun split [] = [[]]
|   split [x] = [[x]]
|   split [a, b] = if a < b then (* here *) else (* here *)
|   split (a::b) = if a < hd b then (* here *) else (* here *)

This question really stuck me.

1 Answers
Related