Learn from Haskell - Functional, Reusable JavaScript | Hacker News Reader

Learn from Haskell - Functional, Reusable JavaScript

seanhess.github.com

139 pointsembwbam48 comments

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/

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.

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.

'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.

... 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".

Also, the definition of an infinite list of ones

    ones = 1 : ones

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

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.

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

> 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.

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.

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.

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

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

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

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

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

You could probably put a trampoline around it.

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));
     };
   };

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.

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.

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

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?

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.

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

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

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

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

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.)

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?

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

    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).

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.

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.

> 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

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]);

Also using underscore, with sortBy:

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

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;
  });

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

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.)

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)

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. :)

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.

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...

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

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

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

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.

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

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.

Reply on news.ycombinator.com