CODEWITHSUNDEEP
sml
sa ma
sa ma

Reputation: 135

SML: how to listify list to sublist

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.

Upvotes: 4

Views: 1943

Answers (1)

John Coleman
John Coleman

Reputation: 52008

Under the assumption that this is homework, I hesitate to give a complete answer, but here are a few hints:

1) In the empty basis case I think that you want to return [[]] rather than []. Your specification doesn't address this, but since the empty list is the longest list of nondecreasing integers which can be pulled from the front of the empty list, the return value should be the list consisting of the empty list. This is somewhat similar to the fact that the powerset (set of all subsets) of the empty set is the set containing the empty set rather than the empty set itself. It shouldn't really matter how you define this particular case, since the real basis case is ...

2) In the [x] case you really need to return [[x]] rather than [x] since the type of the function that you are trying to write is int list -> int list list

3) In the remaining case you can write the pattern like

|    split (x::y::zs) = (* fill this in *)

then test if x <= y to decide what to do. Since both x <= y and x > y will involve split (y::zs) you could compute this once, giving this a name in a let binding and have the if in the scope of that binding, though that is mostly a matter of taste.

Note how the pattern works in this last case. Explicit use of hd should be fairly rare in function definitions which use pattern-matching (though if you flesh out the last case without using a pattern-matching let binding you will be forced to use it in at least one of the branches of the if).

On Edit: Since this isn't homework, here is a complete implementation:

fun split [] = [[]]
|   split [x] = [[x]]
|   split (x::y::zs) =
    let val first::rest = split (y::zs) in
        if x <= y then
            (x::first) :: rest
        else
            [x]::first::rest
    end;

Upvotes: 3

Related Questions