Back to Questions
1.4k
views6
comments
namespaces and scope
f#functional

So I'm trying to put my hand back into functional programming, as it's been nigh on six years since I even LOOKED at something that wasn't imperative and statically typed. Unfortunately, the transition has been a lot more bumpy than I recall.

For example, I'm taking some old LISP code that I did in college, and trying to translate it to F# (that's usually how I start learning languages). In this case, it's part of a collection of functions that simplify equations, such that something like:

1

(2x / x) * y

is turned into

1

x * y.

One of the functions does a variable substitution, and the LISP code goes like this:

1
2
3
4

(defun applyone (sub patt)
     (cond ((null patt) nil)
           ((atom patt) (if (eq patt (car sub)) (cdr sub) patt))
           (t (cons (applyone sub (car patt)) (applyone sub (cdr patt))))))

I've gotten this far, and I could easily swear in a court of law that this is wrong, but I have NO idea why.

1
2
3
4

let rec applyone sub patt =
    match patt with
    | sub.Head -> patt
    | head::tail -> applyone sub head @ applyone sub tail

When I plug that into fsi, I immediately get an error telling me that "The namespace or module 'sub' is not defined," which is nuts, because it's passed into the rotten function!

There is clearly a hole in my understanding thus far, and nothing that I've read has filled it in yet. So I humbly submit myself to the instruction of my functional betters.

DC

.

Hi DC,

In a typed language you will need to define your type of terms: this can be very general or very specific, depending on your needs. A binary tree is a common choice, modelled using:

1
2
3
4
5
6
7

 

type 'a tree = 
    | Tip of 'a 
    | Node of 'a tree * 'a tree

though you might also have a particular expression type in mind, e.g.

1
2
3
4
5
6

 

type expr = 
    | Var of string 
    | App of expr * expr

etc. For the first your substitution function would be:

1
2
3
4

let rec subst v t patt =
    match patt with
    | Tip x ->  if (v=x) then t else patt
    | Node (l,r) -> Node (subst v t l, subst v t r)

For more details on pattern matching and F#/OCaml you might like to read Jason Hickey's OCaml book, which is good for those coming from Lisp, and also the draft chapters of Expert F# at [link:blogs.msdn.com]. I would also encourage you to use Visual Studio 2005 - the F# plugin type checks your code interactively and you'll find yourself much more productive as a result - no deciphering type errors from FSI! There are a range of 90 or 180 day trial versions of Visual Studio 2005 available from [link:msdn2.microsoft.com] (the Express editions are sadly not suitable since they don't accept plugins), and you have the F# plugin already.

Don

By on 3/21/2007 3:18 PM ()

Actually, looking at this example, I still have a couple of questions:

1
2
3
4

let rec subst v t patt =
    match patt with
    | Tip x ->  if (v=x) then t else patt
    | Node (l,r) -> Node (subst v t l, subst v t r)

1. Where did 'x' come from? It wasn't passed into the function. Is this checking to see if patt is of type Tip?

2. What are 'v' and 't'? In the original function, a substitution was passed in (such as '(x a), meaning that all occurrences of x should be replaced by a) along with the pattern to be checked for substitutions (such as '(+ x x)).

I knew getting back into functional programming was going to be rough, but I was definitely not prepared for this level of strangeness!

DC

By on 3/22/2007 8:21 AM ()

Hi DC,

This is simple pattern matching as found in any typed functional laguage. There are many examples of pattern matching in the initial chapters of the books above.

1. "Tip x" is a pattern, checking to see if the input tree is a tip (i.e. a leaf). The input tree is what you called "patt", a name I kept in the example code. If the match is successful then "x" gets the value carried at the leaf of the tree.

2. "v" and "t" are your "x" and "a". If it helps we can rename them:

let rec subst x a patt =
match patt with
| Tip x2 -> if (x=x2) then a else patt
| Node (l,r) -> Node (subst x a l, subst x a r)

Don

By on 3/22/2007 9:56 AM ()

Okay, that makes more sense. Thanks.

DC

By on 3/22/2007 10:47 AM ()

BTW another common tree type is 

1
2
3
4
5

 

type 'a tree = Tree of 'a * 'a tree list

and similar variations on this.

By on 3/21/2007 3:24 PM ()

Thanks for the help! I've read a couple of the draft chapters, but I haven't given them a lot of time to sink in. I've found that I have the most luck learning a new language if I try to translate other programs into the new language, then adapt them to the features of the new language.

I'll definitely have to pick that book up.

DC

By on 3/22/2007 7:57 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