Back to Questions
3.0k
views13
comments
Sorting and Tree in pure functional way
f#functional

Hello,
I am F# noob (learning it for a week or so) and I was thinking, how to implement e.g. Binary Tree, or just Bubble sort in pure functional way. Without changing of value (not using mutable), etc. and I didn't solve it.
Could anyone give me a hint?

.

Also, see the end of this post for an example of a functional bubble sort (and for examples of removing for/while loops in favor of tail recursion). Note that while the sort itself carries no mutable state, it operates against a mutable array, which would be easy to fix by cloning the array first.

By on 6/27/2009 8:39 AM ()

something like this?

[link:vernagus.blogspot.com]

By on 6/26/2009 2:05 PM ()

something like this?

[link:vernagus.blogspot.com]

Thanks, the Binary Tree on this blog is very good.
On that blog, there is also implementation of Stack, so I wrote Stack on my own. I tried to write it as simple as possible, what do you think guys?
Here it is:

//STACKtype Stack = | Empty | Link of int * Stack let isEmpty = function | Empty -> true | _ -> false let rec push = function | x, Link(y, m) -> Link(y, push(x, m)) | x, Empty -> Link(x, Empty) let rec pop = function | Link(x, l) when l <> Empty -> Link(x, pop l) | Link(x, Empty) -> Empty | _ -> Empty let rec top = function | Link(x, m) when m <> Empty -> top m | Link(x, m) when m = Empty -> printfn "Top of the stack: %A" x | _ -> () let s1 = Link (0, Link(1, Link(2, Link(3, Empty))))printfn "Stack s1: %A\nisEmpty: %b" s1 (isEmpty s1)let s2 = Emptyprintfn "Stack s2: %A\nisEmpty: %b" s2 (isEmpty s2)let s3 = push(111, s2)printfn "Stack s3: %A\nisEmpty: %b" s3 (isEmpty s3)let s4 = push(222, s1)printfn "Stack s4: %A\nisEmpty: %b" s4 (isEmpty s4)top s1let s5 = pop s1printfn "Stack s5: %A\nisEmpty: %b" s5 (isEmpty s5)

By on 6/27/2009 12:26 PM ()

Implementing stacks and linked-lists yourself is a great way to learn about functional programming. However, just to let you know, the List type (linked list) is built into the language. Refactoring the other examples here using the built-in list type gives:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#light

let isEmpty = function
    | [] -> true
    | _  -> false

let push x s = x :: s

let pop = function
    | x :: s -> s
    | [] -> failwith "pop: empty stack."

let top = function
    | x :: s -> x
    | [] -> failwith "top: empty stack."

let rec iter f s =
    if not (isEmpty s)
    then
        f (top s)
        iter f (pop s)
    else
        ()

> 
val isEmpty : 'a list -> bool
val push : 'a -> 'a list -> 'a list
val pop : 'a list -> 'a list
val top : 'a list -> 'a
val iter : ('a -> unit) -> 'a list -> unit


> 
let s = [] |> push 3 |> push 2 |> push 1 |> push 0

iter (fun v -> printfn "%A" v) s


> 
val s : int list

0
1
2
3

Note further that there are built-in higher-order functions, like "iter" above, for iterating, mapping, searching, and otherwise transforming Lists, Sequences, Maps, and Sets.

For example, List.iter produces the same output as "iter" above:

1
2
3
4
5
6
7
8
9
10

List.iter (fun v -> printfn "%A" v) s
 

> 
val s : int list

0
1
2
3
By on 7/1/2009 12:54 PM ()

Hi,

That's a good beginning. I have a few comments:

* your type should be generic: "type Stack<'a> = ..."

* isEmpty could be written: let isEmpty x = x = Empty (or even: let isEmpty = (=) Empty )

* your top function should return a value (instead of printing it). It will be easier to use in real code.

* for the push function, it's a better style to write a function with two arguments instead of one tuple (it enables partial application)

* push, pop and top shouldn't be recursive. You should add values on top

(rather than on bottom).

Here is how I would write it:

type Stack<'a> =

| Empty

| Link of 'a * Stack<'a>

let isEmpty x = x = Empty

let push x s = Link(x, s)

let pop = function

| Link(_, s) -> s

| _ -> Empty // you could throw an exception here

let top = function

| Link(x, _) -> x

| _ -> invalidArg "top" "Empty stack"

Tests (yes, I like the pipe operator):

let s = Empty |> push 3 |> push 2 |> push 1 |> push 0

s |> top |> printfn "%A"

s |> pop |> top |> printfn "%A"

s |> pop |> pop |> top |> printfn "%A"

As an exercise, you could now try the Queue type (this time, you'll probably need recursive functions).

Laurent.

By on 6/29/2009 1:54 PM ()

Hi,

I'm learning immensly from this thread. Thanks everyone. One question, how do I change the pop function so pop returns the last value in, and takes it out of the stack.

Many thanks.

Joe

By on 11/28/2009 8:36 AM ()

Because a functional Stack would be immutable, you could rewrite pop to return a tuple composed of the head value and the remaining stack:

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

let pop = function
    | x :: s -> x, s
    | []     -> failwith "pop: empty stack."
    

let myStack = [1; 2; 3]

let h, s = pop myStack

printfn "%d" h // 1
printfn "%A" s // [2; 3]
printfn "%A" myStack // [1; 2; 3]
By on 12/21/2009 5:32 AM ()

Hi,

That's a good beginning. I have a few comments:

* your type should be generic: "type Stack<'a> = ..."

* isEmpty could be written: let isEmpty x = x = Empty (or even: let isEmpty = (=) Empty )

* your top function should return a value (instead of printing it). It will be easier to use in real code.

* for the push function, it's a better style to write a function with two arguments instead of one tuple (it enables partial application)

* push, pop and top shouldn't be recursive. You should add values on top

(rather than on bottom).

Hello,
with generic, you mean that when declaring Stack type, I use 'a instead of int in 'Link'?
Here I changed Top (returns value) and Push(can be curried) functions as you suggested:

let rec push2 x s = match s with
| Link(y, m) -> Link(y, push(x, m))
| Empty -> Link(x, Empty)

let rec top2 = function
| Link(x, Empty) -> x
| Link(x, m) -> top2 m
| _ -> -1

Your implementation seems to me quite nice. I haven't learned about '|>' operator yet, so I am not sure how exactly does it works.Why do you guys think, recursion is not suitable for this case? Just because its slower when adding to end?

By on 7/1/2009 8:20 AM ()

I haven't learned about '|>' operator yet, so I am not sure how exactly does it works.

The forward pipe operator (|>) is defined as follows:

1
2
3
4
5
6

let (|>) g f = f g

>

val ( |> ) : 'a -> ('a -> 'b) -> 'b

All it does is take the left-side argument and apply it to the function specified on the right. What this does, though, is allows the compiler to see the type of the left-side argument BEFORE the function on the right, and this often helps the type-inferrer figure out types on the right-side.

Here is an example from my last post, rewritten with forward-pipe (though there is nothing for the type inferrer to do, it is considered "better" F# style).

1
2
3
4
5
6
7
8
9
10

s |> iter (fun v -> printfn "%A" v)

>
0

1

2

3

Why do you guys think, recursion is not suitable for this case? Just because its slower when adding to end?

<i>If for no other reason<i> than it is (very significantly) slower. You will traverse the entire list <i>every time you get top<i>, which makes the difference between running in O(1) vs O(n^D), where D is the stack depth.

By on 7/1/2009 1:06 PM ()

I think the ``top'' function returns the bottom of the stack. Also, I prefer the construction of ``pop'' to the ``top'', because there is no need for the when clause:

1
2
3
4
5
6
7
8

let rec bottom = function

               | Link(x, Empty) -> x

               | Link(x, m)  -> bottom m

               | Empty -> Empty

It seems to me like a pretty clean implementation of a stack.

By on 6/29/2009 1:26 PM ()

I think the ``top'' function returns the bottom of the stack. Also, I prefer the construction of ``pop'' to the ``top'', because there is no need for the when clause:

1
2
3
4
5
6
7
8

let rec bottom = function

               | Link(x, Empty) -> x

               | Link(x, m)  -> bottom m

               | Empty -> Empty

It seems to me like a pretty clean implementation of a stack.

'Top' function of stack should return last added (top) item. It does in my implementation. But you are right as well, because in fact, returned item is bottom item in this Stack. It was my intention do code it like this and this way is best suitable for recursion. I think this data structure behaves like Stack, even if doesn't look so. :)

Yes, 'when' clause is useless here.

By on 6/30/2009 9:53 AM ()

I should have looked a little closer. I assumed that you were adding to the front in O(1), as in Laurent's implementation. As it is, your implementation adds and pops in O(n), always acting on the back.

Anyway, if you implement a queue you'll see that either enqueue or dequeue should be O(n). But, not both. (And, you'll still get to use recursion without it being superfluous).

Good luck.

By on 6/30/2009 2:48 PM ()

I think the ``top'' function returns the bottom of the stack. Also, I prefer the construction of ``pop'' to the ``top'', because there is no need for the when clause:

1
2
3
4
5
6
7
8

let rec bottom = function

               | Link(x, Empty) -> x

               | Link(x, m)  -> bottom m

               | Empty -> Empty

It seems to me like a pretty clean implementation of a stack.

'Top' function of stack should return last added (top) item. It does in my implementation. But you are right as well, because in fact, returned item is bottom item in this Stack. It was my intention do code it like this and this way is best suitable for recursion. I think this data structure behaves like Stack, even if doesn't look so. :)

By on 6/30/2009 9:52 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