How could we compute the length of a list? Without worrying yet about what lambda-calculus implementation we're using for the list, the basic idea would be to define this recursively:
- the empty list has length 0
- any non-empty list has length 1 + (the length of its tail)
+> the empty list has length 0
+
+> any non-empty list has length 1 + (the length of its tail)
In OCaml, you'd define that like this:
In Scheme you'd define it like this:
- (letrec [(get_length (lambda (lst) (if (null? lst) 0 (+ 1 (get_length (cdr lst))))))]
+ (letrec [(get_length
+ (lambda (lst) (if (null? lst) 0 [+ 1 (get_length (cdr lst))] )) )]
... ; here you go on to use the function "get_length"
)
Some comments on this:
- 1. `null?` is Scheme's way of saying `isempty`. That is, `(null? lst)` returns true (which Scheme writes as `#t`) iff `lst` is the empty list (which Scheme writes as `'()` or `(list)`).
- 2. `cdr` is function that gets the tail of a Scheme list. (By definition, it's the function for getting the second member of an ordered pair. It just turns out to return the tail of a list because of the particular way Scheme implements lists.)
+1. `null?` is Scheme's way of saying `isempty`. That is, `(null? lst)` returns true (which Scheme writes as `#t`) iff `lst` is the empty list (which Scheme writes as `'()` or `(list)`).
+
+2. `cdr` is function that gets the tail of a Scheme list. (By definition, it's the function for getting the second member of an ordered pair. It just turns out to return the tail of a list because of the particular way Scheme implements lists.)
+
+3. I alternate between `[ ]`s and `( )`s in the Scheme code just to make it more readable. These have no syntactic difference.
-What is the `let rec` in the OCaml code and the `letrec` in the Scheme code? These work like the `let` expressions we've already seen, except that they let you use the variable `get_length` *inside* the body of the function being bound to it---with the understanding that it will there refer to the same function that you're then in the process of binding to `get_length`. In OCaml:
+What is the `let rec` in the OCaml code and the `letrec` in the Scheme code? These work like the `let` expressions we've already seen, except that they let you use the variable `get_length` *inside* the body of the function being bound to it---with the understanding that it will there refer to the same function that you're then in the process of binding to `get_length`. So our recursively-defined function works the way we'd expect it to. In OCaml:
let rec get_length = fun lst ->
if lst == [] then 0 else 1 + get_length (tail lst)
In Scheme:
- > (letrec [(get_length
- (lambda (lst) (if (null? lst) 0 (+ 1 (get_length (cdr lst))) ) )i
- )] (get_length (list 20 30)))
+ (letrec [(get_length
+ (lambda (lst) (if (null? lst) 0 [+ 1 (get_length (cdr lst))] )) )]
+ (get_length (list 20 30)))
; this evaluates to 2
If you instead use an ordinary `let` (or `let*`), here's what would happen, in OCaml:
Here's Scheme:
- > (let* [(get_length
- (lambda (lst) (if (null? lst) 0 (+ 1 (get_length (cdr lst))) ) )
- )] (get_length (list 20 30)))
+ (let* [(get_length
+ (lambda (lst) (if (null? lst) 0 [+ 1 (get_length (cdr lst))] )) )]
+ (get_length (list 20 30)))
; fails with error "reference to undefined identifier: get_length"
Why? Because we said that constructions of this form:
2. If you tried this in Scheme:
- > (define get_length
- (lambda (lst) (if (null? lst) 0 (+ 1 (get_length (cdr lst))) ) ))
+ (define get_length
+ (lambda (lst) (if (null? lst) 0 [+ 1 (get_length (cdr lst))] )) )
- > (get_length (list 20 30))
+ (get_length (list 20 30))
You'd find that it works! This is because `define` in Scheme is really shorthand for `letrec`, not for plain `let` or `let*`. So we should regard this as cheating, too.