Scheme question

[GnuVince]

OK, the name of the forum hasn't officially changed yet, but all functional language/programming discussion should come here.

I have written two functions:
nth: returns the nth element of a list.
lfind: returns the position of an element in a list starting from the left.

Now, these two functions are quite similar, so I was wondering, is there a more generic way of writing them?


(define (nth pos lst)
(define (find-it pos cur lst)
(if (eq? cur pos)
(car lst)
(find-it pos (+ cur 1) (cdr lst))))
(find-it pos 0 lst))


(define (lfind elem lst)
(define (find-it elem pos lst)
(if (eq? (car lst) elem)
pos
(find-it elem (+ pos 1) (cdr lst))))
(find-it elem 0 lst))


As you can see, the only differences (besides variable names) are in the if expression and the "then" part.

Thanks for the help.

[jemfinch]

Yeah, you can do that.

I'm going to leave the implementation of this in Scheme as an exercise for you, since I can't guarantee anything about my Scheme abilities.

Here's the code in SML (you should be able to figure it out from knowing O'Caml):


(* Implemented as I would implement it in SML, simply because I wrote it before I remembered I needed to write my functions like you did :) *)
fun nth (_, []) = raise IndexError
| nth (0, hd :: tl) = hd
| nth (i, hd :: tl) = nth (i-1, tl)

fun lfind (_, []) = raise IndexError
| lfind (0, hd :: tl) = hd
| lfind (i, hd :: tl) = lfind (i-1, tl)
(* Ok, end that. Now I've come to another realization: this can't be done in a stictly typed language. Oh well. I'll have to work with my Scheme skizills. *)


Oops. Let's go Scheme. Basically, what you're going to want to do is write a higher-order function that takes a predicate, which is a function that returns a bool. That function will return another function that does either nth or lfind (or whatever else you want to do via your predicate. In a non-general way, see as follows:


(define (nth-predicate i)
(lambda (pos elt) (if (eq? pos i) elt nil)))

(define (lfind-predicate ref-elt)
(lambda (pos elt) (if (eq? ref-elt elt) pos nil)))

(define (p-iterator p?)
(letrec
(f (lambda (l) (if (p? (car l)) (car l) (f (cdr l)))))))

(define (nth i) (p-iterator (nth-predicate i)))

(define (lfind elt) (p-iterator (lfind-predicate elt)))


I'm sure you can get the idea from that example. If I were to define something like this in SML, I'd do it using a foldli function (something normally provided for arrays, but not for lists):


local
fun _foldli idx f init [] = init
| _foldli idx f init (hd :: tl) = foldli (idx+1) f (f ((idx, hd), init)) tl
in
val foldi = foldli 0
end


Since the return type of the function given to foldl(i) doesn't have to be the same as the type of the elements in the list, you could do this type-safely. And you would probably want to return an option of some sort in the case of failure. The only problem with this method is that you couldn't short-circuit the process and return before you've iterated through the whole list -- nth 1 would iterate through the whole list every time. One way to get around that would be to write folds that required accumulators to return either NONE or SOME result, and when SOME result is returned, the fold would stop iterating and just return result. I think I'll do that when I get a working computer back.

Anyway, I digress. Sorry if there are any errors in my code; I'm (a) typing it into a stupid little IE box, and (b) not able to test the code as my computer is down. Give me (and everyone else) a shout if you discover any problems.

Jeremy

[sans-hubris]

jemfinch, you're code doesn't take into account that GnuVince's two different function have two different return types. Besides, you're missing an operand for p?.

Here's what you need, GV: you need a generic function (you could call it p-iterator like jemfinch) that takes two things as operands: the test and the return function. nth and lfind should then be defined with those two things.

PS Sorry for being pedantic, but I think people should use the lambda operator more often. Using the lambda operator more clearly defines something as being a function.

[GnuVince]

sans-hubris: what do you mean in your post scriptum?

Using the form:

(define plus-one
(lambda (n)
(+ n 1)))


instead of this?

(define (plus-one n)
(+ n 1))


Is that it?

[sans-hubris]

Originally posted by GnuVince
sans-hubris: what do you mean in your post scriptum?

Using the form:

(define plus-one
(lambda (n)
(+ n 1)))


instead of this?

(define (plus-one n)
(+ n 1))


Is that it? That's exactly what I mean.

[phubuh]

Real programmers use defun.

:P

[jemfinch]

Originally posted by sans-hubris
jemfinch, you're code doesn't take into account that GnuVince's two different function have two different return types. Besides, you're missing an operand for p?.


My Scheme is horrible, I'll admit that freely :)

Basically, the contract I was trying to have was this: that if the predicate returns anything but nil, return that, if the predicate returns nil, then continue with the iteration. So I meant to take into account the two different return types (which is why, originally, I said "this can't be implemented in a statically typed language") but didn't because my Scheme abilities aren't :)

Here's something of what I'd do in SML (again, I can't test this because I have no interpreter handy):


local
fun helper f idx [] = NONE
| helper f idx (hd :: tl) =
case f (idx, hd) of
NONE => helper f (idx+1) tl
| x => x
in
fun partialFoldl f l = helper f 0 l
end

(* Better style, I think.:
fun partialFoldl f = let
fun helper i [] = NONE
| helper i (hd :: tl) =
case f (i, hd) of
NONE => helper (i+1) tl
| x => x
in
helper 0
end

Also, rather than the case statement, this might be better:

fun partialFoldl f = let
fun helper i [] = NONE
| helper i (hd :: tl) = let
val v = f (i, hd)
in
if Option.isSome v then v else helper (i+1) tl
end
in
helper 0
end
*)

fun nth idx = partialFoldl (fn (i, elt) => if i = idx then SOME elt else NONE)

fun lfind element = partialFoldl (fn (i, elt) => if element = elt then SOME i else NONE)


That's basically the same idea as I was trying to implement in Scheme; if the predicate is finished, it'll return SOME returnValue, otherwise it'll return NONE, and the iteration will continue.

Jeremy