Why is my function of type 'a list * 'a list -> 'b list?

Question

I think I want it be be of type 'a list * 'a list -> 'a list .

intersection should return the intersection of two lists sample input and output:

intersection ([1],[1]);
- [1]
intersection ([1,2,3],[1,2]);
- [1,2]
intersection ([[2,3],[1,2],[2,3]], [[1],[2,3]]);
- [[2,3]]

my function:

fun intersection (l1, l2) = let
    fun intersection_acc (acc, [], h::t) = []
        | intersection_acc (acc, h::t, []) = []
        | intersection_acc (acc, h::t, h2::t2) = if in_list (h, l2)
            then intersection_acc (h::acc, t, l2)    
        else intersection_acc (acc, t, l2)
    in intersection_acc ([], l1, l2)
end

I don't think in_list is the problem, but that looks like this:

 fun in_list (x, []) = false
    | in_list (x, y::r) = if x = y 
    then true 
    else in_list (x, r);

Why did you tag this as matlab? This is obviously some ML variant, not matlab. I'm guessing SML? — sepp2k
Sorry, I didn't realize there was a difference. This is SMLNJ I think. — Nate
@Nate: ML has nothing to do with matlab. ML is a functional language, MatLab is imperative. — Ben Voigt
I feel silly... I assumed ML was MatLab. Sorry about that confusion. — Nate
"ML" as the language family name comes from "meta language". The first ML variant was invented by Robin Milner and others to be the meta language of a proof environment. To this day, several proof environments are written in some ML variant, and tactics for Coq can be provided as OCaml functions (I don't know about the others). — Pascal Cuoq

hugomg hugomg · Accepted Answer · 2011-10-29T23:59:34

My guess is that you botched the base case in your accumulator function

intersection_acc (acc, h::t, []) = []

it should probably return something depending on acc:

intersection_acc (acc, h::t, []) = acc

The reason the 'b list shows up is because intersection will always return the empty list []. Since you don't use that empty list the compiler needs to be conservative and say that the list could be of any type.

In any case, your function seems to be fundamentally more confused. You actually want to do something like

result = []
for each item in list1:
    if item in list2:
        add item to result
return result

Translating this imperative code to a recursive function with an accumulator parameter:

fun go(acc, []) = acc
  | go(acc, x::xs) =
        if x in list2 then
            go(x::acc, xs)
        else
            go(acc, xs)

For the full function:

fun intersect(list1, list2) = let
    fun go(acc, []) = acc
      | go(acc, x::xs) =
            if x in list2 then
                go(x::acc, xs)
            else
                go(acc, xs)
    in go([], list1)

Why is my function of type 'a list * 'a list -> 'b list?

1 Answers