sutton036

Alessandro Stamatto recently asked a question on Stack Overflow about the current state of Haskell's hash tables following our rediscovery last year that Haskell's hash tables were up to 32× slower than common alternatives like C++ and .NET and even slower than Python. Don Stewart edited Alessandro's original question , deleting the citation to the original study that provided a verifiable experiment with complete code, before writing an answer claiming that " the original citation doesn't present any code or benchmarks ". Although Don provided a variety of Haskell-based performance measurements, he omitted any measurements of decent hash table implementations like those readily available from C++ or any .NET language that are still 10× faster than anything that can be written in Haskell. Norman Ramsey's answer took this a step further by drawing the conclusion that "functional data structures perform pretty well" despite the overwhelming evid...

This recent paper describes the state-of-the-art in Data Parallel Haskell (DPH). Some of the code referred to in the paper is available here . This post is in response to a question from one of the coauthors, Roman Leshchinskiy, asking what is wrong with the paper. The problem with this paper is, in a word, cache . Specifically, the widespread adoption of CPU caches two decades ago forced a change in the way programmers traverse data structures when performance is of interest. The old style was to iterate directly using a for loop. The new style is either a cache aware set of loops that exploit knowledge of the sizes of caches in the machine, or a cache oblivious style that uses divide and conquer to subdivide the problem until it fits in-cache regardless of the cache's size. This paper uses neither of the modern approaches, opting instead to use direct loops that have not been seen in real numerical code for several decades. The paper incorrectly asserts that these are "wi...

Bugspy asked an interesting question on Stack Overflow recently: It is a wonderful, very fast, mature and complete language. It exists for a very long time and has a big set of libraries. Yet, it appears not to be widely used. Why ? I suspect it is because it is pretty rough and unforgiving for beginners, and maybe because its lazy execution makes it even harder Jeff Atwood, cofounder of Stack Overflow, has since closed the question for being subjective and argumentative. Sadly, Marc Gravell chose to edit my answer and delete half of my comments so the discussion no longer makes sense. However, my response will be of interest to anyone considering gambling their own money on Haskell so I shall repeat it here. The first point of interest is Norman Ramsey's meta-answer which was written from his point of view as an academic. Norman explains why he believes that major institutes have already made "great use" of Haskell: "Don't tell that to Credit Suisse or Standa...

Here's Markus Mottl's OCaml translation of Okasaki's purely functional leftist heap: module LeftistHeap (Element : ORDERED) : (HEAP with module Elem = Element) = struct module Elem = Element type heap = E | T of int * Elem.t...

The compiler development series of articles in The OCaml Journal have culminated in an example front-end compiler targetting HLVM that now supports variants and pattern matching in addition to previous features. These new language features have been implemented using only a few lines of code, bringing the front-end up to only 253 lines of OCaml code! This new functionality allows substantially more complicated ML-style programs to be written, including the following symbolic simplifier: # type expr = Int of int | Var of int | Add of expr * expr | M...

For around 30 years, the ML family of languages have been characterised by several unusual features including a novel and powerful higher-order module system. This language feature was pioneered by Dave MacQueen in the early 1980s and found its way into the Standard ML and OCaml languages. Higher-order modules allow one module to be parameterized over another module in the form of functors that map modules to modules. Higher-order modules turn out to be especially useful for parameterizing concrete data structures over more primitive data structures. Perhaps the most compelling application of higher-order modules comes from graph theory, where they allow algorithms over graphs to be abstracted over the concrete data structures used to represent the graphs. This application was discussed in our most recent OCaml Journal article " The A* algorithm " that describes a generalization of Dijkstra's shortest path algorithm that is widely used for route finding in game AI. Th...

The Mathematica programming language has many unusual characteristics, two of which are: Everything is an expression. Pattern-based rewrite rules are obscenely powerful. These kinds of characteristics are the foundation of what makes Mathematica a powerful programming language. For example, the bubble sort algorithm can be implemented in a single line without a loop in Mathematica using a single conditional rewrite rule that exchanges adjacent elements when they are out of order: bubble[xs___, x_, y_, ys___] := bubble[xs, y, x, ys] /; x > y This definition causes a new rewrite rule to be injected into Mathematica's global table of rewrite rules. Mathematica then applies this rule to any subexpression it sees that has the form bubble[..] . The pattern on the left side of the rule searches for a pair of adjacent arguments ( x and y ) to bubble where x>y . If the pattern matches then the expression is rewritten such that x and y are exchanged. This example not only demonstra...