tags:

views:

181

answers:

3

The Edison API and Core modules are the Haskell implementation of Purely Functional Data Structures

Do the F# and native .Net data structures cover use cases in the Edison API and Core sufficiently?

Would there be any benefit to trying to port the API and CORE Haskell modules to F#?

+4  A: 

I didn't follow the link, though I have at least a tiny familiarty with the work or Okasaki. So this whole answer is wildly speculative (I may be off base in my assumptions about what's in the Edison API).

I expect there is 'some benefit' in the sense that people like 'reference implementations of common FP data structures' in 'new languages' to help learn new languages.

As for the use in practice (rather than pedagogy), I expect that some of them are useful, though there are some F# and .Net APIs that may be as useful or more useful for many scenarios. The main couple 'batches' of overlapping functionality I would guess are the F# immutable collections (Set and Map), as well as the .Net 4.0 concurrent collections (like ConcurrentQueue).

Of course you'll also find some snippets on the web, like Jomo's immutable queue.

Brian
+5  A: 

I haven't read the paper on edison, but if it's nothing more than the Haskell implementation of Purely Functional Data Structures, doesn't it make more sense to port the SML code that's in the book / thesis? It should be easier than porting Haskell code, which must be annotated for strictness, while F# will have to annotated for laziness.

The language used by the book is SML with syntax extensions for lazy evaluation. F# provides half of those extensions natively:

> let x = lazy 12;;
val x : Lazy<int> = <unevaluated>
> match x with
  | Lazy(n) -> n;;
val it : int = 12
> x;;
val it : Lazy<int> = 12

To convert the book's fun lazy notation, change this:

fun lazy plus ($m, $n) = $m + n

To this:

let plus (m',n') = lazy (
  match (m',n') with
  | (Lazy(m), Lazy(n)) -> (lazy (m + n)).Force())

(See page 33 in the book). The differences from between SML and F# are minor syntax, so the translation should be easy.

As for whether it's worthwhile, most of the data structures in Okasaki's book are very specialised, so they are unlikely to exist already in .NET, even as F#'s immutable Set and Map. It would be worthwhile for the people that need those data structures.

Nathan Sanders
+3  A: 

Revisiting this question months later, I note that

http://lepensemoi.free.fr/index.php/tag/purely-functional-data-structures

someone has implemented lots of them on that blog.

Brian