Back to Questions
3.1k
views8
comments
CL to F# translation
f#lisp

Hi.
I've been trying to replicate an implementation of quicksort in common lisp in F#.
It's not my lisp code (some guy called swisspig or something), just trying to translate it for practice.
The funny thing is, it seems to need a basis to terminate in F#, but not in CL.
The lisp code looks something like this:

(defun quicksort (list)
(let* ((x (car list)) (r (cdr list)) (fn (lambda (a) (a<x))) )
(append (quicksort (remove-if-not fn r)) (list x) (quicksort(remove-if fn r))) ))

I formulated it into F# like this:

1
2
3
4
5
6
7

 
let rec quickSort list =
    if (List.length list) = 0 ithen []
    else quickSort (List.filter(fun item -> item < (List.head list)) (List.tail list)) @ [(List.head list)] @ quickSort(List.filter(fun item -> item >= (List.head list)) (List.tail list))

let x = quickSort[5;8;1;3;6;2;9;4;7]
let y = printf "%A" x

It's a bit messy, but as far as I can see the recursive line is exactly the same, functionally, as the lisp implementation.
This returns an empty list runtime error without the basis.

I think this is probably due to a difference in the way 'append' and '@' work. In particular, 'append' joins together a variable number of lists whereas (each) '@' only joins two, I think.

Alternatively, or as well, it could pertain to a difference between the filter and remove-if.
Or, I could have just made a mistake!

Does anyone have any ideas as to what exactly might account for the difference?

Thanks!

.

I think your code works; in any case, List.concat is more like the LISP append. Here's the version I wrote that's a more idiomatic translation:

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

 

(*
(defun quicksort (list)
   (let* ((x (car list)) (r (cdr list)) (fn (lambda (a) (a<x))) )
   (append (quicksort (remove-if-not fn r)) (list x) (quicksort(remove-if fn r))) ))
*)

let rec quicksort list =
    match list with
    | [] -> []
    | x::r ->
        let fn a = a < x
        List.concat [quicksort (r |> List.filter fn); [x]; quicksort (r |> List.filter (not<<fn))]

let r = quicksort [7;3;5;6;1;4;2]
printfn "%A" r
By on 4/1/2010 3:02 PM ()

Thanks, and that's nice code.
I particularly like the fact that you can pattern a list into head::tail like that.
Interestingly though, it still does include a basis, if I am reading it right... |[] -> []
I actually don't know why the CL version doesn't need one - maybe there's some kind of basis implicit in 'append' or something like that.
Thanks again!

By on 4/1/2010 3:37 PM ()

In CL, if you have the empty list, the "car" and "cdr" don't throw an exception, they just return the empty list again. In F#, these (head/tail/pattern-match-with=::) throw.

By on 4/1/2010 3:50 PM ()

That's a good point. I remember from the little I've read that CL, in want of any other resolution, resolves to nil.
But what I wonder about more in the example is that there is any resolution at all.
For instance if I try something like this:

(defun infinitelist (L)
(cons(car L) (infinitelist(cdr L)) ))

I get "Program stack overflow" because it does not have a basis to return at null.
In other words, car<> and cdr<> return <> but a recursive funcall on <> keeps on returning <> ad finitum.
I still don't see how the quicksort does not cause a stack overflow.
I think it might have something to do with 'append' but I'm not sure to be honest.
I could just be missing something.

By on 4/1/2010 4:49 PM ()

For instance if I try something like this:

(defun infinitelist (L)
(cons(car L) (infinitelist(cdr L)) ))

I get "Program stack overflow" because it does not have a basis to return at null.
In other words, car<> and cdr<> return <> but a recursive funcall on <> keeps on returning <> ad finitum.
I still don't see how the quicksort does not cause a stack overflow.

Quicksort as it stands is not tail-recursive, and so on a big enough data, both the (fixed) CL and F# versions will stackoverflow. But it needs to be a very big list.

(That said, yes, looking more carefully back at your original CL code, it does just loop infinitely until stackoverflow, without a base case to prevent the recursive calls.)

By on 4/1/2010 5:13 PM ()

Great, thanks for the advice, the F# code, and the points about stack overflow, tail-recursion etc.
Sorry again about the dodgy code to begin with.

By on 4/2/2010 4:15 AM ()

actually scratch that, I think it might need a basis in CL too, which makes sense
i think i had a basis in a calling function
that's what i get for sprawling code
sorry about that
(how do you make the very-ashamed smiley?)

By on 4/1/2010 5:05 PM ()

by the way,
sorry about the formatting glitch - I got the F# formatting but that was the expense!

By on 4/1/2010 2:54 PM ()

    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