Paper Info
Title
A functional implementation of the garsia--wachs algorithm: (functional pearl)
Abstract
This functional pearl proposes an ML implementation of the Garsia-Wachs algorithm. This somewhat obscure algorithm builds a binary tree with minimum weighted path length from weighted leaf nodes with given inorder. Our solution exhibits the usual benefits of functional programming (use of immutable data structures, pattern-matching, polymorphism) and nicely compares to the purely imperative implementation from The Art of Computer Programming.
Year
DOI
Venue
2008
10.1145/1411304.1411317
ML
Keywords
Field
DocType
computer programming,ml implementation,garsia-wachs algorithm,functional implementation,weighted leaf node,binary tree,imperative implementation,functional programming,obscure algorithm,wachs algorithm,minimum weighted path length,functional pearl,polymorphism,zipper,data structure,pattern matching
Data structure,Functional programming,Path length,Computer science,Binary tree,Algorithm,Theoretical computer science,Zipper,Computer programming
Conference
Citations 
PageRank 
References 
1
0.36
5
Authors
1
Name
Order
Citations
PageRank
Jean-Christophe Filliatre1644.65