hubFS: THE place for F#

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?

something like this?
http://vernagus.blogspot.com/2007/10/purely-functional-data-structures-f_14.html

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.

---

"It seems that perfection is reached, not when there is nothing left to add, but rather when nothing more can be taken away." -- Antoine de St. Exupéry

none:

something like this? http://vernagus.blogspot.com/2007/10/purely-functional-data-structures-f_14.html

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:

//STACK

type 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 = Empty

printfn "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 s1

let s5 = pop s1

printfn "Stack s5: %A\nisEmpty: %b" s5 (isEmpty s5)

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:

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.

Hi,

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

* your type should be generic: "type Stack = ..."

* 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 =
| Empty
| Link of 'a * Stack

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.

none:

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: 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. :)

none:

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: 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.

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.

LLB:

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?

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:

#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:

List.iter (fun v -> printfn "%A" v) s
<FONT size=1> </FONT>

>
val s : int list

0
1
2
3

---

"It seems that perfection is reached, not when there is nothing left to add, but rather when nothing more can be taken away." -- Antoine de St. Exupéry

Ville183:

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:

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).

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

>
0

1

2

3

Ville183:

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

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

 

---

"It seems that perfection is reached, not when there is nothing left to add, but rather when nothing more can be taken away." -- Antoine de St. Exupéry

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

 

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

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]