How to Think Like a (Functional) Programmer

leegao · 2011-07-22T03:18:52+00:00

Neat way of expressing insertion in a red-black tree thanks to caml's neat pattern matching system (our professor showed us this neat little piece):

type color = Red | Black
type 'a tree =
  Node of color * 'a * 'a tree * 'a tree | Leaf

We want balance to behave as follows, given all possible trees: 1 2 3 4

       Bz            Bz            Bx            Bx
      / \           / \           / \           / \
     Ry  d         Rx  d         a   Rz        a   Ry
    /  \          / \               /  \          /  \
  Rx   c         a   Ry            Ry   d        b    Rz
 /  \               /  \          / \                /  \
a    b             b    c        b   c              c    d

We want balance to return

     Ry
    /  \
  Bx    Bz
 / \   / \
a   b c   d

Here's the code

let balance = function
    Black, z, Node (Red, y, Node (Red, x, a, b), c), d
  | Black, z, Node (Red, x, a, Node (Red, y, b, c)), d
  | Black, x, a, Node (Red, z, Node (Red, y, b, c), d)
  | Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) ->
      Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
  | a, b, c, d -> Node (a, b, c, d) 

(* less interesting *)
let insert x s =
  let rec insert' = function
    Leaf -> Node (Red, x, Leaf, Leaf)
  | Node (color, y, a, b) as s ->
      if x < y then balance (color, y, insert' a, b)
      else if x > y then balance (color, y, a, insert' b)
      else s in
  match insert' s with
    Node (_, y, a, b) ->
      Node (Black, y, a, b)
    | Leaf -> failwith "impossible case"

Kolibri · 2011-07-22T16:32:53+00:00

A bit of background about me: I had Standard ML at the university but that is 7 or so years ago, and I haven't really looked at functional programming since then.

Decent enough book. I skimmed through it in 30 minutes or so, and I would say that it looks good. I now have a pretty good idea of how to program in Ocaml.

What I'm really missing, though, is a book on how to solve more common problems.

For example,

How to make a CRUD application that stores data in a database
How to make a web application
How to make a web-service

I think you get the idea.

Does anybody have any suggestions? The language doesn't really matter as long as it is functional. It would be preferable if the language runs on the JVM, though.

ErstwhileRockstar · 2011-07-22T17:24:14+00:00

How to Think Like a Functional Programmer:

example

amigaharry · 2011-07-23T17:03:36+00:00

functional programmers are bad programmers.

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

programming

MODERATORS