Learn from Haskell - Functional, Reusable JavaScript(seanhess.github.com)

139 pointsby embwbamvor 14 Jahren48 comments

seanhess.github.com

Learn from Haskell - Functional, Reusable JavaScript

http://seanhess.github.com/2012/02/20/functional_javascript.html

10 comments

agscalavor 14 Jahren

The article mentions it already, but if this style of programming piques your interest and you don't know about underscore.js, it's absolutely worth your time to check it out:

http://documentcloud.github.com/underscore/

freyrs3vor 14 Jahren

One might as well say "Learn from Lisp" or "Learn from ML" as there really isn't anything Haskell specific about these kind of higher order functions. If we want to learn from Haskell, the big ideas are functional purity and its type system.

noblethrashervor 14 Jahren

The biggest idea is probably laziness.

In Haskell, everything is basically a function. Even the number 3 is really just a function that if and when evaluated will return the value 3. I used that concept to to simply some JavaScript UI code a while back. I had SELECT element that I needed to populate dynamically but wanted the last option to invoke an action that allowed the user to add another option

     choice 1
     choice 2
     choice 3
     <add new choice>

I ended up populating the dropdown list using a bunch of javascript functions that looked like this

    function () { return { key: 1, value: 'choice 1' } }
    function () { return { key: 2, value: 'choice 2' } }
    function () { return { key: 3, value: 'choice 3' } }
    function () { /* do stuff that creates a new choice */ }

Not sure I would have thought of that if I had not first played with Haskell and grokked laziness.

tumultvor 14 Jahren

'In Haskell, everything is a function' is absolutely wrong. People who don't know much about Haskell often say this. There's a post by Conal Elliott about this incorrect meme: http://conal.net/blog/posts/everything-is-a-function-in-hask...

It's simply not true. In fact, because Haskell is statically typed, it's very easy to tell what's a function and what's not: If its type doesn't have an -> in it, it's not a function.

noblethrashervor 14 Jahren

... I know that 3 is not literally function in the Haskell type system but it's an easy way to explain it to people less familiar with the language (not that I assume freyrs3 is one of those).

Also, while it might be true that "people who don't know much about Haskell" often say that everything is a function, it's also the case that people who do know a lot about the language find the notion to be pedagogically useful: On page 13 of The Haskell School of Expression, Paul Hudak offers that pi (which is of type Floating a => a and thus clearly not a function) "can be thought of as a function with no arguments".

alipangvor 14 Jahren

Also, the definition of an infinite list of ones

    : ones

is a non-function value, but is recursively applied to itself. Might help illustrate why this is a useful notion in Haskell.

lurker14vor 14 Jahren

To be precise.

"ones" is not "recursively applied to itself". "ones" is not a function. "(:)" is a function.

In actuality, "ones" is both an argument and a result of the (:) function (aka "cons").

This works in Haskell because "ones" is not an atomic value or function; "ones" is a "lazy" structure, where some of the elements's values depend on other element's values, and Haskell uses a "call-by-need" graph reduction algorithm to evaluate arbitrarily complex* computations down to values, not in any sort of sraihtforward order suggested by "argument -> function -> result -> lvalue" in an imperative or strict language.

Laziness is at the core of the runtime system's model for computing a result from a program, and it's not something you can translate line-by-line from a non-lazy program, even a functional language program.

I'm not just being pedantic. Haskell (with a runtime like GHC, required for this conversation to really make sense) really is different from other programming systems. ("Programming system"! Not just "language"!).

The runtime system ("RTS") is not just a C runtime that provides a statement language and shim over OS system calls.

The RTS is not "just" a VM like Java VM.

The RTS is (metaphorically) like perl's "perl -nple" or a SQL RDBMS query planner, where the runtime is itself a program that takes your code as input and does its own extremely sophisticated computation that is not at all visible in your program's code.

[] Arbitrarily* complex, but still "causal" structures that admit at least one valid order of evaluation. Trying to define "ones = ones" or other non-disentanglable cyclic dependencies leads to a runtime failure ("<loop>" exception).

[] In some cases, the graph solver might practically fail to solve a graph that is theoretically solvable. Let's ignore that.

gtanivor 14 Jahren

That's good info, GHC is an pretty amazing feat of engineering, there are some good summaries of STG, C--, etc for further reading:

http://darcs.haskell.org/ghc/docs/comm/the-beast/stg.html

http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler...

http://www.reddit.com/r/programming/comments/i4jb1/haskells_...

-------------

Also, Simon M started Google +ing about what he's up to

https://plus.google.com/u/0/107890464054636586545/posts

tikhonjvor 14 Jahren

I think by function you really mean "thunk", which is just the name for an unevaluated expression. A thunk is really just an implementation detail while a function has important semantic meaning (it is a mapping from values of one type to values of another).

A thunk can be thought of as a procedure with no arguments (taking some terminology from SICP), and in JavaScript procedures are called "functions", but using JavaScript's terminology in a Haskell context gets confusing.

Additionally, it wouldn't even be correct to say all Haskell values are thunks. You actually have a fair bit of control over this and can have strict, unboxed elements and the like with GHC. A different compiler could implement the non-strict semantic in a different way.

noblethrashervor 14 Jahren

I meant function in the same sense that JavaScript means function which is not the same as what Haskell considers to be a function (since JS functions don't have to return a value). I should have been more precise.

freyrs3vor 14 Jahren

> Even the number 3 is really just a function

Haskell doesn't define integers as functions, they are machine integers just like most other languages. You may be thinking of the Peano numbers, which do have a particularly nice representation in Haskell but they certainly aren't used by default.

dinedalvor 14 Jahren

I like this style of programming, but isn't there cause for concern in having such a deep call stack in JS?

gcrvor 14 Jahren

Yes. V8 and other JS compilers optimize tail calls, but it's not guaranteed by the standard. (i think IE doesn't, for example)

mhansenvor 14 Jahren

I'm not sure where you got this idea. V8 does not optimize tail calls. It's easy to see this in the Chrome console, I just entered this now:

  var a = function(x) { if (x == 0) return 'done'; return a(x-1); };
  a(100000);
  RangeError: Maximum call stack size exceeded

http://code.google.com/p/v8/issues/detail?id=457

gcrvor 14 Jahren

Wait, seriously? I didn't know that. Thanks for the link!

Guess it's time for me to stop relying on that behavior...

eruvor 14 Jahren

You could probably put a trampoline around it.

twfarlandvor 14 Jahren

The currying function shown can be made more flexible:

   var _slice = Array.prototype.slice;

   var curry = function() {
     var args = _slice.call(arguments);
     return function() {
       var args2 = _slice.call(arguments);
       return args[0].apply(this, args.slice(1).concat(args2));
     };
   };

As can the composition func:

   var compose = function(f, g) {
     return function() {
       var args =_slice.call(arguments);
       return f(g.apply(this, args));
     };
   };

DanWaterworthvor 14 Jahren

I'm been experimenting with UHC's js backend. One of the things that struck me was that in Haskell if I have a function like:

    forever :: Monad m => m a -> m a

I can use it for either asynchronous or synchronous javascript, e.g

    forever :: IO a -> IO a
    forever :: ContT r IO a -> ContT r IO a

The same function can take a synchronous js function or an async js function and run it in an infinite loop. For this reason, I think that if you want to learn from Haskell in writing reusable js then you should look into monads.

Martijnvor 14 Jahren

Small nitpick, the type of forever is actually:

  forever :: Monad m => m a -> m b

Since it never returns a value, the resulting monadic action can be polymorphic in its return type.

jacobrvor 14 Jahren

Great article, I learned a lot from http://blog.jcoglan.com/2011/03/05/translation-from-haskell-... as well.

axvor 14 Jahren

One bit of trouble I have with functional style programming is something like the following example: if I have an array of people with firstName and lastName properties, how would I go about returning the person with the longest full name without adding any properties directly to the objects? It is a simple map then reduce to return the maximum length, a fairly trivial modification thereof to return the full name, but when I want to return the original object, I can't think of a good way to do this.

The best I can figure is first mapping to a nested array where the first element is the object and the second is the computed property but that seems really messy. Thoughts?

samdkvor 14 Jahren

The map is unnecessary. Just reduce:

    (* assuming: val total_len : string -> int *)

    List.reduce seq ~f:(fun a b ->
      if (total_len a) > (total_len b) then a else b)

It's not necessary in this case, but fold is often a lot more useful than reduce. At least the way I think of it, the type of reduce is 'a list -> ('a -> 'a -> 'a) -> 'a, whereas the type of fold is 'a list -> init:'b -> ('b -> 'a -> 'b) -> 'b. The upside is that you can construct basically any type of thing you'd like, since 'b is a completely different type. The downside is that if 'a is different than 'b, you need some sort of initial value to give it.

edit: Yes, this does require you to compute string length multiple times...but keep in mind that getting string length is very cheap in languages with good strings. (That is, basically everything except C's null-terminated strings.) 99% of the time it's not going not going to matter at all. If you do care, you can map to a tuple of (original_struct,total_len) and then do the reduce and then another map to get back to your original structure, or use a fold, as I mentioned, or write a (tail-)recursive function that does it in slightly fewer operations. (Although I don't think JS has tail-call optimizations, so that's probably a bad idea if you're doing it in JS.)

adimitrovvor 14 Jahren

    Yes, this does require you to compute string length multiple times...but keep in mind that getting string length is very cheap in languages with good strings. (That is, basically everything except C's null-terminated strings.)

Since this is a discussion about Haskell, too, I feel obliged to say that computing the length of a String type in Haskell is an O(n) operation, because String is really just

    type String = [Char]

i.e. a linked list of Char values.

Typically, if you want performance out of strings in Haskell, you'll use the Text or ByteString types BUT the length operation of Data.Text is still O(n). Only ByteString offers

    length :: ByteString -> Int

Which is O(1).

eruvor 14 Jahren

You can use a reduce/fold here, but it goes against the notion of building your program up from smaller pieces. Functional people call this composability, normal people call it code reuse.

reduce/fold is a very general and powerful tool. In general you want to use the most specific and least powerful solution you can get away with. This spares the reader some thinking, and in theory gives the compiler more leeway. Also with less power there's less room for error.

Here a combination of maximum (or maximumBy in Haskell) and map will give you what you are looking for.

axvor 14 Jahren

Aren't I then computing the value of total_len for my largest object numerous times? That was why I went for the map, it made some sense to pre-compute the lengths and then find the largest one. Certainly I could implement some caching mechanism but that would come with some implementation complexity?

Raphael_Amiardvor 14 Jahren

Like in a procedural language, you can precompute and keep the results. It's still more concise. I use Ocaml's tuples here to make a pair of the length/object but you could use a struct/object/array/whatever:

    let precomp = List.map lst (fun el -> ((length el), el)) in
        let get_max (l1, el1) (l2, el2) = el1 if l1 > l2 else el2 in
            List.reduce lst get_max

jfagervor 14 Jahren

You don't need a map, just a reduce (foldl, really). Using underscore, no double calculation:

    _.reduce(arr, function(p1, p2) {
        var len = p2.firstName.length + p2.lastName.length;
        return (len > p1[1]) ? [p2, len] : p1;  
    }, 
    [null, -1]);

woobyvor 14 Jahren

Also using underscore, with sortBy:

    _.chain(people)
    .sortBy(function(person) { 
      return person.firstName.length + person.lastName.length; })
    .last()
    .value()

mhansenvor 14 Jahren

FYI, this isn't as general, but I think it shows off underscore quite nicely:

  _(people).max(function(person) {
    return person.firstName.length + person.lastName.length;
  });

ufovor 14 Jahren

The pattern you mention of using a tuple of key-value pairs is not that bad and it even has a name. The Perl people call it the Swartzian transform.

An alternative if you don't like that would be having the maximum-finding function receive an additional comparator argument, similarly to qsort.

telemachosvor 14 Jahren

> The Perl people call it the Swartzian transform.

Yup, though one small thing: it's 'Schwartzian transform'[1] for Randal Schwartz.

[1] http://en.wikipedia.org/wiki/Schwartzian_transform

gcrvor 14 Jahren

In racket, I'd write something like

  (argmax (λ(c) (string-length (customer-name c)))
          customers)

http://docs.racket-lang.org/reference/pairs.html?q=argmax#(d...)

Haskell has argmaxBy: http://hackage.haskell.org/packages/archive/list-extras/0.3....

If your language doesn't have argmax, fold the list with the best value, like this in lisp:

  (define (my-argmax fun lst)
    (foldl (λ(prev-max elt)
             (if (< (fun prev-max) (fun elt))
                 elt
                 prev-max))
           (car lst)
           (cdr lst)))

No extra space usage, no temporary values, no sorting; all in O(N) time. :)

nicklovescodevor 14 Jahren

  longestName = maximumBy . comparing $ \(f,l) -> length $ f++l

eruvor 14 Jahren

That doesn't fit the bill. He was looking for comparison on a structure that holds more than just the name. (Though the right answer is very similar to what you've written.)

neutronicusvor 14 Jahren

You wouldn't use map or reduce, you'd just use recursion with an accumulator.

If you absolutely insist on map/reduce, you can just use reduce, where your binary function returns whichever object has a longer full name.

rapalavor 14 Jahren

Well, reduce is a recursion with an accumulator. Did you had something special in mind?

axvor 14 Jahren

In hindsight the second solution was obvious :) But can you explain your ideal solution more? Is it something that can be accomplished in Javascript?

eruvor 14 Jahren

Why would you write mind-boggling recursion by hand, and not use a nice combinator that comes pre-debugged?

neutronicusvor 14 Jahren

Because I had a brain fart and though "reduce" was "scan", and I didn't want to initialize an array.

eruvor 14 Jahren

In Haskell there are some helper functions for these:

    longestLastname :: [Person] -> Person
    longestLastname names = maximumBy (comparing (length . lastname)) names

In general, you can do map something like

    extractProperty list = map (\x -> (f x, x)) list

Then work on the first element of the tuple (comparing for sorting etc), and at the end return the original object by extracting the second element of the tuple.

sgk284vor 14 Jahren

Similar in spirit to the Haskell and Lisp examples, here it is in Python:

    people = [Person('foo', 'bar'), Person('John', 'Doe'), Person('Jane', 'Anonymous')]
    key = lambda person: len(person.first_name + person.last_name)
    max(people, key=key)

peteretepvor 14 Jahren

Funnily enough, it was learning Javascript that made my Perl use a lot more higher-order functions, so when it came to Haskell, I was already on that page...

arnoooooovor 14 Jahren

What bothers me in this with pure JS is the verbosity of "function (arg1,arg2) {return ...;}"

dmmalamvor 14 Jahren

coffescript's sugar is pretty nice (haskell inspired)? function (a,b) {return a+b} becomes (a,b) -> a+b Hopefully in harmony we will see a shorter function syntax for environments where CS isn't an option

udpvor 14 Jahren

Not having to write `function` everywhere is pretty much the reason I started using CoffeeScript.

feinvor 14 Jahren

Why not just save snippets? I do this in emacs (yasnippet) all the time instead of constantly rewriting the same stub.

Not knocking coffescript here, just saying that "I don't want to write a specific word" is a pretty terrible reason to pick any language over another.

eruvor 14 Jahren

I guess he also doesn't want to read it everywhere and clutter up his code.

embwbamvor 14 Jahren

The idea is that once you define "apply" and its like, you don't have to write function () { return; } inline any more. You just use library-level functions and partially apply them. These techniques reduce the number of anonymous functions you create.

_gingerhendrixvor 14 Jahren