Back to Questions
8.5k
views16
comments
Apparently, I don't understand pattern matching
f#

Okay, maybe I'm assuming that I can do something I can't, but this is really starting to frustrate me. Here's a little example.

1
2
3
4
5

let rec diffTypes testThing =
    match box testThing with
    <b>| :? </b>string as x -> x
    <b>| :?</b> list<b><</b>string<b>> as </b>s -> diffTypes s.Tail
    <b>| </b>_ -> "denied";;

Alright, now here's what my brain tells me this should do. A variable call testThing comes in and is boxed into type 'obj'. Then its underlying type is tested against type 'string'. If the variable is a string, it's printed out, and everything is done. If not, it's then tested against the type 'list<string>'. If it's a list of strings, we go back through with the first element of the list thrown away.

First, I know there is a bug here, in that s.Tail always returns a list. That much doesn't matter for the purposes of the example, unless I am seriously mistaken.

What doesn't make sense is that the function comes out listed as 'val diffStuff : string list -> string'. That implies to me that it will REQUIRE a string list to come in, when what I WANT is to be able to pass in either one and figure out what it is when it gets inside.

I seriously doubt this is a deficiency of the language, it's just something that hasn't clicked in my brain. The only problem is that there seem to be an alarming number of things about all this that aren't clicking.

DC

.

Hi DC,

Recursive calls in F# always imply a type constraint on the thing being called: that's how type inference works. Because you're making a recursive call type inference assumes that the thing you're calling requires a list.

Try this instead 

1
2
3
4
5
6
7
8
9

 

let rec diffTypes (testThing : obj) : string =
    match testThing with
    | :? string as x -> x
    | :? list<string> as s -> diffTypes (box s.Tail)
    | _ -> "denied";;

I've added the type annotations to help you see the type of the thing you've defined - you might like to add these to help you think about what the type of the function you want to write is.

As you can see, there is a serious difference between writing a function of type "obj -> obj", "obj -> string", "List<obj> -> obj" etc. Normally the types will be quite specific, and "obj" types occur relatively rarely. Programming with heterogeneous objects and lsits is fairly rare in F#, but as you see it's totally possible to do it.

Cheers!

don

By on 4/6/2007 3:12 PM ()

What, then, is the more "F#" way of doing what I'm trying to do? I agree that using 'obj' for all my types is probably not the best way to about things.

DC

By on 4/6/2007 6:26 PM ()

I think it's quite hard to say what is a more F# way of doing this without knowing what your trying to achive. Although generally F# programers prefer to user the patten matching over list syntax as it is very powerful - allowing you to have cases for list with a specific number of items, match for specific constants or pull an number of items of the head of a list at the same time. Here's a shot demo of this from the book "Foundations of F#":

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#light
let rec findSequence l =
    match l with
    | [x; y; z] -> 
        printfn  "Last 3 numbers in the list were %i %i %i" 
            x y z
    | 1 :: 2 :: 3 :: tail -> 
        printfn "Found sequence 1, 2, 3 within the list"; 
        findSequence tail
    | head :: tail -> findSequence tail
    | [] -> ()

let testSequence = [1; 2; 3; 4; 5; 6; 7; 8; 9; 8; 7; 6; 5; 4; 3; 2; 1]

findSequence testSequence

The fact that .Tail always returns a list is not a bug, the tail of a list is always a list which maybe empty, the head of a list is always an element, if you where looking to get the last item in a list you would look for the case where the tail is empty and take the head - quite easy to say if you use the list pattern matching syntax. Suprisingly easy to say when you use the list pattern matching syntax:

1
2
3
4
5
6

#light
let rec last_element l =
    match l with
    | [x] -> x
    | head :: tail -> last_element tail
    | [] -> failwith "empty list: no last element"

As bonus this function type is 'a list -> 'a meaning we know what type will be returned from the type of the list.

By on 4/6/2007 8:52 PM ()

Okay, the problem with my thinking, then, is that I'm expecting to be able to write a recursive function that could take more than one type of argument.

The head/tail thing makes perfect sense, since that's the way LISP always does things. I was mostly just trying to get validation that what I was seeing was right.

It seems like the type inference is what is stopping me from having a function like this work:

let rec substitute sub patt =
match patt with
| head::tail -> substitute sub head + substitute sub tail
| x -> if(fst sub=x) then snd sub else x;;

What this should do (that is, what it did when I wrote the equivalent LISP function) is this: sub is a tuple of values to be substituted, so that ("a", "b") would mean that you wanted to replace all occurrences of "a" with "b" in patt. If patt is a list, you break out the head and tail, and run the substitution again. In every case, when the function that was given the head is run, that non-list value should be checked against the substitution pattern, and if it matches, it should be substituted according to the rule in sub. Basically, patt is decomposed, element by element, and then reconstituted with the substitutions.

Unfortunately, it seems like I can't make one recursive function that takes an argument of variable type. I could always make two functions, one that substitutes for single elements and another that takes the list, but I'm somehow convinced that this sort of thing should be possible. Maybe there is a major difference between F# and LISP that I'm not considering, but since I'm not considering it, I have no idea what it is or how to get around it.

DC

By on 4/17/2007 8:36 AM ()
1
2
3
4
5

let rec substitute sub patt =
    let aux value = if (value = fst sub) then (snd sub) else value
    match patt with  
    | hd :: tl -> (aux head) :: substitute sub tl
    | [] -> failwith "empty list"

You call 

1

substitue sub head

while <head> is of type 'a (while <tail> is of type 'a list), hence there is a type error. Indeed, you now have two types definitions that conflict, one called in 

1

substitue sub patt

of type 

1

val substitute : ('a * 'a) -> 'a list -> 'a list

, and 

1

substitue sub head

of type 

1

val substitute : ('a * 'a) -> 'a -> 'a list

, hence the error.

Moreover, (+) is not (as far as I know, but I may be wrong) a list concatenation operator.

Last, note that 

1

| x -> if(fst sub=x) then snd sub else x;;

means that sub is of type 'a list * 'a list and not 'a * 'a. Indeed, since x must be of the same type as head::tail, x is an 'a list. Hence fst sub must return an 'a list, and thus sub must be a ('a list * 'a list).

I hope this helps (and that it's not wrong )

By on 4/17/2007 10:14 AM ()

I understand the type error, but the fact that I can write a pattern set that addresses the possibility of either type being passed in makes me think that variable-type arguments have to be possible. Otherwise, what's the point of matching on types?

I'm pretty sure that 

1

| x -> if(fst sub=x) then snd sub else x;;

applies to a tuple as well, because I can constrain the type to (sub: 'a*'a), and I don't get any type errors about it. The concatenation operator may be a source of my problems, but I could swear that '+' was used to add an element to the front of a list.

Edit: I just looked it up, and you're right, I should be using '@' and '::'.

DC

By on 4/17/2007 10:28 AM ()

You don't have to match on different types (as in int vs string). You can discrimate on the patterns of a simple type. For instance, if you want to implement a factory pattern, you may use

1
2
3
4
5
6
7

type args = A of int | B of (int*int) | C of (int*int*float)

let make args =
  match args with
    | A x -> float_of_int x
    | B (x, y) -> float_of_int (x + y)
    | C (x, y, z) -> (float_of_int (x + y)) * z

You may also wish to create simple types such as type Point = Coord of (int * int), and then use active patterns to create such types from an xml file.

Matching against types is just one possibility. And it can be used for 'obj types. Say, for instance, that you receive an 'obj array as an argument, you may want to do different things depending on the actual type.

Here is a very simple example function :

1
2
3
4
5

let debug x =
  match (box x) with
    | :? string as s -> print_string s
    | _ -> print_any x
  print_string "\n"
By on 4/17/2007 10:44 AM ()

I've decided to give up trying to figure out F#. It's a great idea, but it's just too obtuse for me to figure out on my own, even with the vast resources available via the Internet. The error message I got while trying to solve this massively frustrating problem was enough to tip the balance:

1
2
3
4
5
6

type args = Pattern of (list<string>) | Element of string

let rec substitute (sub: string*string) patt =
    match patt with
    | Pattern x -> substitute sub (Element(x.Head)) @ substitute sub (Pattern(x.Tail))
    | Element element -> if(fst sub=element) then snd sub else element;;
1
2
3
4
5
6
7
8
9
10

c:\match.ml(19,54): error: FS0001: Type mismatch. Expecting a
        string * 'a list
but given a
        string * string.
The type 'a list does not match the type string

c:\match.ml(19,63): error: FS0001: This expression has type
        string
but is here used with type
        'a list

Those messages are obviously trying to tell me something. They tell me where in the code to go, but I have no clue as to the reason behind the error. Why is it expecting a "string * 'a list"? When did I use an "'a list"? Everything was listed as a string!

Like I said, I applaud the concept and effort, and I'm sure it works extremely well for certain applications and certain people, but I am clearly not one of them.

DC

By on 4/17/2007 11:18 AM ()

Hi DC

Let me walk you through how F# is interpreting your program:

1) "substitute" must return a list, since you concatenate two "substitute" return values in the "Pattern x" case; and concatenation is a list operation. Without any further information on the actual type of the list elements, this return type is inferred as 'a list.

2) The above means that the "Element element" case also has to return an 'a list. This means that both "snd sub" and "element" have to of type 'a list. In the former case, you had already compared the first part of the "sub" tuple to a string, so "sub" itself have to be of type (string * 'a list). Yet you type-annotated it as string*string, hence the first error. The second error is pretty straightforward: "element" is typed as a string, yet you are trying to return it from "substitute" which would mean it is of type 'a list. Hence the second error.

Cheers,

Adam.

By on 4/17/2007 2:48 PM ()

Hi DC

Let me walk you through how F# is interpreting your program:

1) "substitute" must return a list, since you concatenate two "substitute" return values in the "Pattern x" case; and concatenation is a list operation. Without any further information on the actual type of the list elements, this return type is inferred as 'a list.

2) The above means that the "Element element" case also has to return an 'a list. This means that both "snd sub" and "element" have to of type 'a list. In the former case, you had already compared the first part of the "sub" tuple to a string, so "sub" itself have to be of type (string * 'a list). Yet you type-annotated it as string*string, hence the first error. The second error is pretty straightforward: "element" is typed as a string, yet you are trying to return it from "substitute" which would mean it is of type 'a list. Hence the second error.

Cheers,

Adam.

Okay, making a couple of changes to try and deal with those problems yields no useful results. Concatenation being a list operation really doesn't make much sense to me, but I suppose that's a matter of semantics. Using the cons operator, which will let you put elements onto a list (as in 1 :: [2] gives [1; 2]), and doing away with the args type, since it was apparently not doing anything for me, I have this:

1
2
3
4

let rec substitute sub patt =
    match patt with
    | head::tail -> substitute sub head :: substitute sub tail
    | element -> if(fst sub=element) then snd sub else element;;

This gives me three errors instead of the original two. Again, it appears that F# is trying to force everything into a single type, which is frustrating in the extreme.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

c:\match.ml(18,35): error: FS0001: Type mismatch. Expecting a
        'a list
but given a
        'a.
The resulting type would be infinite when unifying 'a and 'a list

c:\match.ml(18,43): error: FS0001: Type mismatch. Expecting a
        'a list
but given a
        'a.
The resulting type would be infinite when unifying 'a and 'a list


c:\match.ml(18,20): error: FS0001: Type mismatch. Expecting a
        'a
but given a
        'a list.
The resulting type would be infinite when unifying 'a and 'a list

What takes this from frustrating to downright evil is the fact that, in one case it tells me it needs a list, then it turns around and tells me that I gave it a list, but it in fact needs an element.

I can't begin to count the number of things I've read about this, trying to figure out what in God's name this is trying to do, and it's just not clicking. The concept of pattern matching makes plenty of sense, and I think I'm pretty good on it. It's type inference, apparently, that makes this all an exercise in high blood pressure.

DC

P.S. Why, when I go to post, do I get a script execution error until I switch to HTML mode and back?

By on 4/18/2007 7:57 AM ()

As said in an earlier post :

=================
You call substitue sub head while <head> is of type 'a (while <tail> is of type 'a list), hence there is a type error.

Indeed, you now have two types definitions that conflict,
substitue sub patt of type val substitute : ('a * 'a) -> 'a list -> 'a list ,
and substitue sub head of type val substitute : ('a * 'a) -> 'a -> 'a list , hence the error.
(actually, see below, it is ('a list * 'a list) -> ..., but I presume that what you attended was ('a * 'a))

=================
Last, note that 

1

| element -> if(fst sub=element) then snd sub else element;;

means that sub is of type 'a list * 'a list and not 'a * 'a.

Indeed, since x must be of the same type as head::tail, x is an 'a list. Hence fst sub must return an 'a list, and thus sub must be a ('a list * 'a list).

By on 4/18/2007 11:51 PM ()

Yeah, that makes no sense.

My original understanding of type inference led me to believe that it could understand a function that might, at different times, take differing types of arguments (a string list instead of a string, for example). Apparently, this is not the case.

I still don't understand why the element clause infers an 'a list. You haven't told me why sub is of type ('a list * 'a) instead of ('a * 'a).

As I said before, there are probably a lot of really ingenious uses for something like this, but it's just too hard to get over the hump on learning it, at least for me. Normal imperative coding (in C#, at least) doesn't require this level of care on the part of the programmer with types, since it's pretty unforgiving about mis-typed variables and makes for a very one-to-one experience when putting things together. My assumption was that F# would be more lenient, since it could more intelligently decide how to type a variable, but all it's done (at least, from reading the explanations here) is require that the programmer remember a really unusual set of inference rules, which sort of defeats the purpose. If the language is going to be smarter, it should be requiring me to deal with fewer rules, not learn new ones.

I don't want to make a flame out of this, because I honestly don't understand the language, and I figure that I'm probably hung up on some small concept that just hasn't clicked in my mind yet. I applaud the efforts that have gone into this endeavor, because I'm pretty sure I couldn't build something like this. So, just to be clear, I'm not bashing the language or the community, I'm just expressing my frustrations with trying to learn this.

DC

By on 4/19/2007 7:52 AM ()

ok, i'll give it a go :)

considering the second (i think it was) version that you corrected to do list concatenation correctly, we have:

1
2
3
4

let rec substitute sub patt =
    match patt with
    | head::tail -> substitute sub head :: substitute sub tail
    | element -> if(fst sub=element) then snd sub else element;;


the first error is

1
2
3
4
5
6
7
8

      | head::tail -> substitute sub head :: substitute sub tail
  -----------------------------------^^^^^

stdin(33,35): error: FS0001: Type mismatch. Expecting a
        'a list
but given a
        'a.
The resulting type would be infinite when unifying 'a and 'a list


...and is caused because lists are constructed as a series of cons operations on an empty list, ie. [1;2;3] is really 1 :: 2 :: 3 :: [] (which groups as (1 :: (2 :: (3 :: []))) -> (1 :: (2 :: [3])) -> (1 :: [2;3]) -> [1;2;3] ). this means that F# thinks that head should be an 'a as it pattern matched to the first element of the 'a list patt, but head should also be an 'a list as you use it in place of patt in the call substitute sub head, and it previously figured out that patt must be an 'a list because of the pattern match against head::tail that you did. when it tries to put these types together it can't come up with a type that is both an 'a and an 'a list at the same time, hence the error.

the second and third errors are due to exactly the same reasoning applied to tail rather than head (in the case of the second error), and to the result of the whole function (in the case of the third).

if i understand you correctly, what you mean to write is the following:

1
2
3
4
5
6
7

let rec substitute sub patt =
    match patt with
    | [] -> []
    | head :: tail ->
        let newhead = if (head = fst sub) then snd sub else head
        newhead :: substitute sub tail
;;


...which gets the inferred type signature:

1

val substitute : 'a * 'a -> 'a list -> 'a list


...ie. it takes a first parameter which is a tuple of two values of some type, a second parameter which is a list of elements of the same type as those in the tuple which is the first parameter, and returns a list of elements of that same type.

it proceeds by first matching patt against the empty list - if patt is empty then simply return an empty list. if patt is not empty, then it is an element (head) "cons-ed" onto a list (tail). in this case, if the value of head equals the first element of the tuple sub then return the second element of the tuple sub (ie. do the replace) cons-ed onto the result of calling substitute on the tail of the list with the same substitution tuple (sub). if the value of head does not equal the first element of the tuple sub then simply return head cons-ed onto the result of calling substitute on the tail of the list with the same substitution tuple (sub).

the result is you can call

1
2
3
4

> substitute ('a','b') [ 'a'; 'b'; 'c' ] ;;
val it : char list = ['b'; 'b'; 'c']
> substitute (1,2) [ 10; 11; 2; 1; 3 ] ;;
val it : int list = [10; 11; 2; 2; 3]


..and even

1
2

> substitute ( [1;2], [5;6] ) [ [3;4]; [-1;10]; [1;2]; [10;11] ] ;;
val it : int list list = [[3; 4]; [-1; 10]; [5; 6]; [10; 11]]


does that help?

cheers,

r.

By on 4/19/2007 8:46 AM ()

Okay, broken out in an almost ludicrously explicit description was exactly what I needed. The mechanism by which F# inferred types made some assumptions I'm not sure I would have made, but I have no doubt that not making those assumptions would turn the whole process into something wildly more complicated.

I guess since F# is bounded somewhat by the requirements of the .NET platform, it has to make some things explicit, and trying to figure out multiple signatures for a function could potentially become an extremely arduous task.

Thanks for the explanation. I'm not sure I'll be able to parse out future things as well as this, but at least I've got something to look back at.

DC

By on 4/19/2007 9:03 AM ()

i am not a Functional Programmer (tm) :) and at the risk of belabouring the point (ie. ignore this if you want)...

with reference to the second point in your reply, F# is not trying to figure out multiple signatures for a given function - it figures out one signature that may be generic (ie. have things of types like 'a, 'b, etc - types we don't know yet but will at call-time).

in the <i>substitute<i> example, the signature is as given - there is only one - but F# only constrains as much as required so it becomes: val substitute : 'a * 'a -> 'a list -> 'a list where 'a can represent things of type int, long, ulong, list<int>, list<list<int>>, list<int*ulong>, list<somecomplicatedrecordtype> or whatever, as inferred at the point the function is called. the requirement is simply that 'a can be only one of those at a time :) the errors you were getting were because it couldn't figure out a type that is both a "thing" (type 'a) and a "list of those same things" (type 'a list) at the same time, except an infinitely recursive type (which it wasn't happy about in this context). eg. if 'a is an int, then we need 'a to also be a list<int>. but then we've just made 'a into a list<int>, so we also need 'a to be a list<list<int>>. and so on... cheers, r.

By on 4/19/2007 9:21 AM ()

May I suggest reading again some F# or OCaml tutorials to better understand pattern matching.

[link:www.ocaml-tutorial.org]
[link:pauillac.inria.fr]
[link:www.cs.caltech.edu]

Or the excerpt chapters from Mr Syme ([link:blogs.msdn.com])

This shall be better explained there than by our brief attempts.

Hope this helps

By on 4/18/2007 12:18 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper