CODEWITHSUNDEEP
smltype-inferencesmlnj
Yuka Langbuana
Yuka Langbuana

Reputation: 125

SML [circularity] error when doing recursion on lists

I'm trying to built a function that zips the 2 given function, ignoring the longer list's length.

fun zipTail L1 L2 = 
    let 
      fun helper buf L1 L2 = buf
        | helper buf [x::rest1] [y::rest2] = helper ((x,y)::buf) rest1 rest2
    in
      reverse (helper [] L1 L2)
    end

When I did this I got the error message:

Error: right-hand-side of clause doesn't agree with function result type [circularity]

I'm curious as of what a circularity error is and how should I fix this.

Upvotes: 3

Views: 676

Answers (2)

sshine
sshine

Reputation: 16105

The problem with circularity shows up many other places.

You want (x::rest1) and not [x::rest1].

The problem is a syntactic misconception.

  • The pattern [foo] will match against a list with exactly one element in it, foo.
  • The pattern x::rest1 will match against a list with at least one element in it, x, and its (possibly empty) tail, rest1. This is the pattern you want. But the pattern contains an infix operator, so you need to add a parenthesis around it.
  • The combined pattern [x::rest1] will match against a list with exactly one element that is itself a list with at least one element. This pattern is valid, although overly specific, and does not provoke a type error in itself.

The reason you get a circularity error is that the compiler can't infer what the type of rest1 is. As it occurs on the right-hand side of the :: pattern constructor, it must be 'a list, and as it occurs all by itself, it must be 'a. Trying to unify 'a = 'a list is like finding solutions to the equation x = x + 1.

You might say "well, as long as 'a = 'a list list list list list ... infinitely, like ∞ = ∞ + 1, that's a solution." But the Damas-Hindley-Milner type system doesn't treat this infinite construction as a well-defined type. And creating the singleton list [[[...x...]]] would require an infinite amount of brackets, so it isn't entirely practical anyways.

Some simpler examples of circularity:

  • fun derp [x] = derp x: This is a simplification of your case where the pattern in the first argument of derp indicates a list, and the x indicates that the type of element in this list must be the same as the type of the list itself.

  • fun wat x = wat [x]: This is a very similar case where wat takes an argument of type 'a and calls itself with an argument of type 'a list. Naturally, 'a could be an 'a list, but then so must 'a list be an 'a list list, etc.

As I said, you're getting circularity because of a syntactic misconception wrt. list patterns. But circularity is not restricted to lists. They're a product of composed types and self-reference. Here's an example without lists taken from Function which applies its argument to itself?:

  • fun erg x = x x: Here, x can be thought of as having type 'a to begin with, but seeing it applied as a function to itself, it must also have type 'a -> 'b. But if 'a = 'a -> 'b, then 'a -> b = ('a -> 'b) -> 'b, and ('a -> 'b) -> b = (('a -> 'b) -> b) -> b, and so on. SML compilers are quick to determine that there are no solutions here.

This is not to say that functions with circular types are always useless. As newacct points out, turning purely anonymous functions into recursive ones actually requires this, like in the Y-combinator.

The built-in ListPair.zip is usually tail-recursive, by the way.

Upvotes: 1

John Coleman
John Coleman

Reputation: 51998

There are a number of problems here

1) In helper buf L1 L2 = buf, the pattern buf L1 L2 would match all possible inputs, rendering your next clause (once debugged) redundant. In context, I think that you meant helper buf [] [] = buf, but then you would run into problems of non-exhaustive matching in the case of lists of unequal sizes. The simplest fix would be to move the second clause (the one with x::rest1) into the top line and then have a second pattern to catch the cases in which at least one of the lists are empty.

2) [xs::rest] is a pattern which matches a list of 1 item where the item is a nonempty list. That isn't your attention. You need to use (,) rather than [,].

3) reverse should be rev.

Making these changes, your definition becomes:

fun zipTail L1 L2 = 
let 
    fun helper buf (x::rest1) (y::rest2) = helper ((x,y)::buf) rest1 rest2
      | helper buf rest1 rest2 = buf

in
    rev (helper [] L1 L2)
end;

Which works as intended.

The error message itself is a bit hard to understand, but you can think of it like this. In

helper buf [x::rest1] [y::rest2] = helper ((x,y)::buf) rest1 rest2

the things in the brackets on the left hand side are lists of lists. So their type would be 'a list list where 'a is the type of x. In x::rest1 the type of rest1 would have to be 'a list Since rest1 also appears on the other side of the equals sign in the same position as [x::rest1] then the type of rest1 would have to be the same as the type of [x::rest1], which is 'a list list. Thus rest1 must be both 'a list and 'a list list, which is impossible.

The circularity comes from if you attempt to make sense of 'a list list = 'a list, you would need a type 'a with 'a = 'a list. This would be a type whose values consists of a list of values of the same type, and the values of the items in that list would have to themselves be lists of elements of the same type ... It is a viscous circle which never ends.

Upvotes: 3

Related Questions