Back to Questions
1.2k
views3
comments
Trees, breadth-first flattening, and good idioms?
f#

In learning F#, I was challenged by a pal to implement a breadth-first flattener. I came up with the following, which I invite everyone to please critique.

One example of the kind of thing that leaves me scratching my head is what I perceive to be a merely stylistic choice of, say, 

1

type 'a node = Node of 'a * 'a node list

vs

1

type 'a node = { payload: 'a; children: 'a node list }

. With the first type, I found it helped to write helper functions for retrieving the payload and the children from a tree node, whereas with the second, the parts are explicitly named. What would a seasoned F#er do? Many thanks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

type 'a node = Node of 'a * 'a node list
let payload n = match n with Node(p,c) -> p
let children n = match n with Node(p,c) -> c

let rec bft n = 
   let rec _bft kids = 
      List.map (fun n -> payload n) kids 
            @ List.fold_left (fun l n -> l @ _bft (children n)) [] kids in
   payload n :: _bft (children n)

let sample = Node("root", [
   Node("a1",[]);
   Node("a2", [
      Node("b1", [
         Node("c1", []);
         Node("c2", [])
      ]);
      Node("b2", [])
   ]);
   Node("a3", [])
])

let flattened = bft sample
// val it : string list = ["root"; "a1"; "a2"; "a3"; "b1"; "b2"; "c1"; "c2"]
.

With the first type, I found it helped to write helper functions for retrieving the payload and the children from a tree node, whereas with the second, the parts are explicitly named. What would a seasoned F#er do? Many thanks

The only gotcha with records is that labels are not first-class, that is, you can't pass labels to functions (to allow, e.g., higher-order record member selection). Stylistically speaking, I tend to use records for code that is more "procedural", or data-structure-oriented, and algebraic types for more "algebraic" code.

In other words, records tend to emphasize naming, ADTs tend to emphasize structure. In the example you present, I'd say that the names of the components aren't very important; maybe you'll convince yourself of this if you rewrote it using records (the "sample" value would be a nuisance to construct with two names per node). Using function to match and introduce names where appropriate:

1

let bft =   let rec _bft kids =     List.fold_left (fun l -> function (Node (_, c)) -> l @ (_bft c))      (List.map (function (Node (p, _)) -> p) kids) kids  in function (Node (p, c)) -> p :: _bft c

After some (mechanical, mostly) rewriting, I'd settle for:

1

let bft =   let rec _bft kids traversal =    List.fold_right (function (Node (_, c)) -> _bft c) kids      (List.fold_left (fun l -> function (Node (p, _)) -> p :: l)        traversal kids)  in function (Node (p, c)) -> List.rev (_bft c [p])

Which is more efficient, thought less transparent.

An alternative would be to use a functional queue. Borrowing from Okasaki (Purely Functional Data Structures, CUP):

1

type 'a queue = 'a list * 'a listlet empty = [], []let is_empty = function ([], _) -> true | _ -> falselet check = function ([], r) -> (List.rev r, []) | q -> qlet snoc (f, r) x = check (f, x :: r)let head = function ([], _) -> failwith "head" | (x :: _, _) -> xlet tail = function ([], _) -> failwith "tail" | (_ :: f, r) -> check (f, r)

Then, the BFS traversal is just (!):

1

let bft n =  let rec traverse q =    if is_empty q then [] else    match head q with Node (p, c) ->      p :: traverse (List.fold_left snoc (tail q) c)  in traverse (snoc empty n)

So, as you can see, it can be more a matter of using the right algorithm.

By on 12/22/2006 2:09 PM ()

Thanks very much for that lovely and erudite reply, which was my introduction to the "function" keyword (which is, IMHO, underdocumented in the F# documentation).

Also, I like the "snoc" name.

By on 12/22/2006 5:12 PM ()

Just for holiday fun, here's the version using the experimental "active patterns" feature. This feature is currently being extensively revised, so this post is not really meant to say "use this", but to indicate how active patterns will help make this sort of code clearer once finalized. Note that NonEmpty is a decomposition function that gets run during pattern matching and replaces the use of is_empty, head and tail.

1
2
3
4
5
6
7
8
9
10

 

let bft n =  
  let rec traverse q =    
      match q with 
      | NonEmpty(Node (p, c),t) -> p :: traverse (List.fold_left snoc t c) 
      | _ -> [] 
  traverse (snoc empty n)

with prelude:

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

 

#light

type 'a node = Node of 'a * 'a node list 

type 'a queue = 'a list * 'a list
let empty = [], []
let is_empty = function ([], _) -> true | _ -> false
let check = function ([], r) -> (List.rev r, []) | q -> q
let snoc (f, r) x = check (f, x :: r)
let query f = { new Experimental.IPattern<_,_> with get_Query() = f }
let NonEmpty<'a> = 
    query (function 
           | (([], _) : 'a queue) -> None 
           | (h :: f, r) -> Some(h,check(f,r)))
By on 12/22/2006 11:16 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