List of lists in SML/NJ given a list and wanting to satisfy a condition. I get problem: An expression of type "'a" cannot have type "'a list"

Dora Boutsini 0
Viewed 24

We have a list such as [1,2,7,5,3,2,8,9] and we want to create a list that includes lists of groups of those numbers so that each group does not have decreasing order of its numbers. For example for the above list the answer is [[1,2,7],[5],[3],[2],[8,9]] because 1<2<7(one group, no decreasing order) [5],[3] different groups because 5>3 etc. I wrote this program in ml and it shows this error :

Elaboration failed: Type clash. An expression of type "'a" cannot have type "'a list" because of circularity.

Where is the error in my code ? Any help will be appreciated! My code is this :

fun final_listify (h::t) = 
  let 
    fun listify [] acc = acc
      | listify (h::t) [[]] = [[h]]
      | listify (h::t) ((h1::t1)::rest) = 
          if h >= h1 then listify t ((h::h1::t1)::rest)
          else listify t (h::(h1::t1)::rest); 
  in 
    listify (h::t) [[]]
  end;
sml typeerror list numbers
1 Answers

Something that immediately jumps out.

     | listify (h::t) [[]] = [[h]]

If your code compiled, on the very first call, it will just return the head element of the input list in a list in a list. The recursion stops at this point. Surely this is not what you want to accomplish.

The problem you're seeing, though, ultimately stems from this line:

         else listify t (h::(h1::t1)::rest);

You're close but not quite there. You want to add a new list containing the head element to the front of the accumulator.

          else listify t ([h]::((h1::t1)::rest));

Now:

final_listify [1, 2, 3, 5, 2, 7];

Yields:

[[7, 2], [5, 3, 2, 1]]

And that just requires a bit of reversing.

I strongly suggest using as to make your code more readable.

fun final_listify lst = 
  let 
    fun listify [] acc = acc
      | listify (h::t) [[]] = listify t [[h]]
      | listify (h::t) (acc as (first as h1::t1)::rest) = 
          if h >= h1 then listify t ((h::first)::rest)
          else listify t ([h]::acc);
  in 
    listify lst [[]]
  end;

As an addendum, we can use a fold to handle the recursion.

fun seq lst =
  List.foldl 
    (fn (x, acc) => 
       case acc of 
         [] => [[x]] 
       | []::tl => [x]::tl
       | (h::hs)::tl =>
         if x >= h then (x::h::hs)::tl
         else [x]::acc)
    [] lst;
userRb2210
Related