What do functional languages (LISP / ML) offer that Julia doesn't?

I picked up some Julia fairly recently. As far as I can see, Julia supports functional programming somewhat better than Python. For example, anonymous functions (lambdas) are not limited to one line, and there is the function pipeline operator |>, which is convenient for composing functions. Still, I’m wondering if there are good reasons for learning “full-fledged” functional languages like LISP, Ocaml, and Haskell. I hear people promoting these languages all the time, but I never studied them.

From some superficial reading online, one of the many unique characteristics of these “full-fledged” functional languages is the use of linked lists as a default data structure, as opposed to arrays in Julia. In Ocaml and Haskell, arrays are available only from the standard library not the core language, while in Julia it’s the exact opposite: you cannot use linked lists unless you use e.g. DataStructures.jl, or write your own implementation. What’s the advantage in using linked lists everywhere, rather than for special problems which require fast insertion and deletion?

Also, a common feature of functional languages is tail call optimization, which promotes a heavily recursive programming style. For what kind of problems is this better than Julia’s programming style?

1 Like

Actual functional programmers may weigh in, but my sense of the consensus on linked lists is that no one really thinks they’re all that. I’m pretty sure they aren’t going to top anyone’s list of reasons they prefer Haskell or OCaml or whatever.

Your point about tail call optimization is much closer to the mark; the design patterns in the functional world tend to be very different than in Julia or Python. They typically use recursion and pattern matching in place of loops and conditionals. Problems involving tree-like data structures are often especially amenable to this style; for example, Pandoc is written in Haskell.

My favorite explanation of this point is this Quora answer by Tikhon Jelvis. He details a particular example (infinite quadtrees) which illustrates the advantages of algebraic data types and laziness quite convincingly, IMO.

Julia does have MLStyle.jl and Lazy.jl, so it is possible to borrow some of the elements of functional programming when you want to. But it isn’t really idiomatic Julia, and the lack of TCO (among many other things) keeps Julia from being a compelling alternative to a Haskell programmer who wants to keep doing things the way they’re done in Haskell. But that’s fine: Julia is for those who find that alternatives aren’t quite doing it for them.

4 Likes

IMO, TCO is a really cool idea but is actually a mistake. Any code that needs TCO can be fairly easily written in a loop, so it’s not that big of an advantage. Furthermore, TCO relies on destroying the stack when tail calls happen. This sounds good, but especially in complicated cases makes de-bugging way harder. Furthermore, TCO isn’t an optional feature. If you are using a language that has it, you can’t ever expect to run code with it disabled, or you will get stack overflows from packages and standard library functions that assume TCO works.

4 Likes

Well, Haskell doesn’t really have loops, so they better have TCO. :slight_smile:

3 Likes

In Haskell at least, lists are often used as iterators rather than as a data structure for storage (see for example this Reddit thread, in particular this answer).

2 Likes

I have no experience with Haskell & Co, but I wonder if their pure functional approach has performance impacts. In this approach, it is not possible to modify data structures (like arrays) in place, which is less efficient due to allocations, right?

I think placing Lisp in the same cohort as Ocaml and Haskell is a bit of misconception.

(Common) Lisp is inherently a dynamically typed imperative interpreted language with first-class functions. Julia is in many ways just a flavor of Lisp with a more familiar syntax.

ML and Haskell are statically type-checked “real” functional languages, which makes the experience very different. Linked lists are a minor difference IMO, strong type guarantees being a more prominent change.

The main advantage of FP is the feeling that “if it compiles, it works” (or, at least, it won’t suddenly crash at runtime). One of the things that FP enforces is exhaustive condition checks in certain cases. Another is a more formal definition of traits via type classes. Say, if you define a numeric type, ideally you’d like to make sure you have all the arithmetics, comparisons and whatnot defined for it. Julia doesn’t check for that, Haskell does.

So, the major advantage of FP is that the type system is designed in order to allow compiler verify whether the programmer checked for all edge cases.

This Reddit answer is an opinion of a person who had experience in both Julia and Haskell of pros and cons of both (TLDR: they are both great, it depends on the specific task who wins).

6 Likes

@sswatson Thanks for linking Tikhon Jelvis’s Quora answer. Some examples, like the lazy quad tree, seems fairly difficult to reproduce in Julia. I think the package Lazy.jl only implements lazy lists, but not lazy trees. On the other hand, I find it fairly easy to use Julia to reproduce the example of simplifying arithmetic expression, and the code is just as short. A stripped down version of the Haskell code is, using algebraic data type and pattern matching,

data Expr = Var String 
          | Lit Integer 
          | Expr :+: Expr
          | Expr :*: Expr  deriving (Show, Eq)

simplify :: Expr -> Expr 
simplify expr 
  | nextStep == expr = expr 
  | otherwise       = simplify nextStep 
  where nextStep = case expr of 
          Var x -> Var x 
          Lit n -> Lit n 
           
          (Lit n1 :+: Lit n2) -> Lit (n1 + n2)
          (Lit n1 :*: Lit n2) -> Lit (n1 * n2) 
 
          (e1 :+: e2) -> simplify e1 :+: simplify e2
          (e1 :*: e2) -> simplify e1 :*: simplify e2

My Julia code is

abstract type Operator end
Math = Union{Operator, Integer}

struct Add <: Operator
    a :: Math
    b :: Math
end

struct Multiply <: Operator
    a :: Math
    b :: Math
end

evaluate(x::Integer) = x
evaluate(x::Add) = evaluate(x.a) + evaluate(x.b)
evaluate(x::Multiply) = evaluate(x.a) * evaluate(x.b)

Now if you run

formula = Multiply(2, Add(4,3))
evaluate(formula)

You’ll get 14, as expected. Of course, the Haskell version is still more flexible, since you can extend the code to treat 0 and 1 differently from other numbers, as in the original Quora post, while Julia only dispatches according to types, not values. Please let me know if you see any other pitfalls of the above Julia code!

3 Likes