Miso

Miso is a tiny library for experimenting with data structures in JavaScript. Its particular focus is purely functional data structures of the type discussed by Chris Okasaki in his (1996) thesis and (1998) book.

Usage

JavaScript interpreters are not generally optimised for functional programming: they do not implement tail recursion optimisation, and the large number of closures required to implement currying, function composition and the like will consume a lot of memory. For these reasons, although I haven't run the performance tests necessary to confirm this, I would not recommend Miso for use in production environments, especially browser-based environments where many clients will be using outdated and inefficient JavaScript interpreters (such as that used by Internet Explorer).

Miso uses various language constructs in its internals that are not implemented by all common JavaScript interpreters (such as Array#forEach). If you want to use Miso in an environment that doesn't support these constructs, please get in touch and I can look at replacing them with alternatives.

Testing

Miso's test suite is written using James Coglan's JS.Test test framework, which is part of his JS.Class library. In order to run the tests you will need a console-based JavaScript interpreter such as V8 or Rhino. To run the test suite, cd into the Miso directory and execute the test-runner file.

v8 runner.js

Roadmap

There are quite few things I'd like to implement, ranging from sugar on some of the more verbose pieces of functionality, through additional library functions, to entirely new data types.

General

• Improve the curry function so that it deals better with more than two arguments.
• Allow higher-order functions to take strings representing operators, which will then be resolved to functions.

Here's an example of how such an operator might be defined:

var OPERATORS = {
  "+": function(a, b) {
    return curry(function(o) {
      return a + o;
    }, b);
  }
};

And here's a use case:

sum = foldl("+", 0);

Miso.List

• init and last functions to complement head and tail.
• [a] -> Bool functions like any and all.
• [Number] -> Number functions like sum, product, maximum and minimum.
• concat, take, takeWhile, and as much else of Haskell's Data.List library as I can be bothered with.

Miso.Set

• Write a binary search tree data type and library functions to traverse and modify it.
• Change Set's underlying element store to the binary search tree. This will require elements stored in a Set to be ordered.
• Implement an ordering API. JavaScript sadly doesn't have typeclasses, so a settled object API will have to suffice; object#compare perhaps.

Bibliography

• Okasaki, C., 1996. Purely Functional Data Structures. Ph.D. Pittsburgh: School of Computer Science, Carnegie Mellon University.
• Okasaki, C., 1998. Purely Functional Data Structures. Cambridge: Cambridge University Press.

Licence

Copyright (c) 2008, Benedict Eastaugh.

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

• Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
• Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
• The name of the author may not be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.