Source
r/haskell•
sid-kap

Code review request: Dijikstra's algorithm

For a school assignment, I'm working on a visualization of Dijikstra's algorithm and several variants of A* search.

I tried to mimic the imperative-style implementation of Dijiksta's found in most textbooks, so I wrote the algorithm in the ST monad and used mutable hashtables and heaps.

Unfortunately, I'm not happy with how the code reads. Unlike in other imperative languages, I feel like the only way to make this algorithm concise is by turning my code into operator soup, with lots of >>=, <*>, and <$>s.

(For example, the following code:

loopCondition = do
  heapNotNull <- not . PQueue.null <$> ST.readSTRef heap
  tNotVisited <- isNothing <$> HT.lookup visited t
  return (heapNotNull && tNotVisited)

whileM_ loopCondition $ -- do stuff

can only be written in one line if we write it as

whileM_ ((&&) <$> (not . PQueue.null <$> ST.readSTRef heap) <*> (isNothing <$> HT.lookup visited t)) $ -- do stuff

which is very ugly, in my opinion.)

What can I do to make my code more readable, especially for imperative programmers? I'm afraid that the world's finest imperative language might not be the world's most readable imperative language.

Code is here. (By the way, if you are interested in running it, graph.hs has a shebang and the stack runghc options, so chmod +x graph.hs; ./graph.hs should work if you have stack installed! The code creates a random graph, runs three variants of A*-search on it, and outputs the visualization to graph.svg.)

Posted Mar 5, 2016, 7:31 PM UTC · edited

2013
ephrion•

What's wrong with your first block? That looks perfectly fine to me. Being concise is good only if it improves readability.

The code overall looks good! Now do it in a purely functional manner and see how it compares.

12
sid-kapOP•

It's a bit hard to convince friends that Haskell is a good language for writing imperative code when it takes four lines to write the equivalent of

while (!heap.isEmpty() && !visited.contains(t))

.

Especially to non-Haskellers, the above one-line statement is straightforward and concise; the equivalent Haskell expression uses both do-notation and fmap, and is harder to parse/comprehend.

It seems to me like functional code can be very readable in Haskell, but imperative code sometimes cannot.

(BTW, I know it's possible to write this using efficient pure data structures. However, I wanted to use mutable hashtables to prove to my non-Haskeller friends that my Haskell implementation is as readable and as efficient as their Java/Python implementations.)

8
cameleon•

You can define your own functions and operators to mimic the imperative code pretty closely.

whileM_ (not <$> isEmpty heap ^&&^  not <$> contains t visited)

(^&&^) = liftA2 (&&)
isEmpty = fmap PQueue.null .  ST.readSTRef
contains e m = isNothing <$> HT.lookup m e

Untested, but you get the idea. If you want, you can probably make the Haskell look almost exactly like the imperative code, but that takes you too close to BASIC in Haskell I think... ;)

8
qualiaqq•

This. Abstracting away details through function extraction into well named functions (e.g. isEmpty), is something I wish people would do more in every language.

7
ephrion•

The main benefits of imperative Haskell are the type safety, the ability to write your own control structures (whileM is just a function etc), that you can specify your effects and how they interact (eg State and Exception can either rollback state or not depending on which is on top) ,and that you can refactor much more easily than in eg C or Java. It's not going to be more concise, usually.

That you can factor out the loopCondition into a regular ol' Haskell value effortlessly is a huge selling point IMO. That's not trivial/easy to do in C, and is much more difficult to reason about in eg Java or Python.

Supplier<Boolean> loopCondition = () -> !heap.isEmpty() && !visited.contains(t))

while (loopCondition.call()) ... // not sure of exact method name

is going to require that all variables captured in the closure are final. Python's methods would support dynamic lookup IIRC but still not quite as easily.

4
normalOrder•

hard to convince friends that Haskell is a good language for writing imperative code

Why is the burden of proof on Haskell? I've never seen a convincing argument from the other side that their way is better than Haskell. In fact, the strongest argument they can come up with for not learning Haskell is that they don't understand Haskell. facepalm.

while (!heap.isEmpty() && !visited.contains(t))

Pretend you've never learned a C-like language and tell me that doesn't look like gibberish. What the hell does "&&" mean? Why do some words start with "!"? What's with the empty parenthesis? Etc.

3
moo_ha_ha•

Why not a self recursive function, though? It will look much better than the monadic version you got.

2
janmas•

Since you are using the monad-loops package, you could also write

 whileM_ (andM [not . PQueue.null <$> ST.readSTRef heap, isNothing <$> HT.lookup visited t]) $ -- do stuff
6
sid-kapOP•

Thanks for pointing this out!

1
AlpMestan•

You might want to take a look at the astar package. for a purely functional implementation.

3
dramforever•

I tried to mimic the imperative-style implementation of Dijiksta's found in most textbooks, so I wrote the algorithm in the ST monad and used mutable hashtables and heaps.

I'm sorry for being impolite, but this is horribly bad. You are trying to use a functional language imperatively. It's sort of like using a dictionary as a hammer, and complaining about it being hard to handle.

Why? Knowledge is power, right?

I'm afraid that the world's finest imperative language might not be the world's most readable imperative language.

The world's finest power, a.k.a knowledge, isn't usable as a hammer at all. :) Seriously, I strongly disagree with Haskell being the "finest imperative language". It's definitely a wrong way to use Haskell.

And if you want to, you might gain some insight reading the implementation of Dijkstra's algorithm in fgl ( https://hackage.haskell.org/package/fgl-5.5.2.3/docs/src/Data-Graph-Inductive-Query-SP.html#dijkstra ). Not the most readable variable names and implementation decisions, I suppose, and it requires a bit deeper understanding of how the library is organized. But I do find it much better more concise than the imperative version without the monadic mess, and you might be able to fix it to your taste.

-2
AndrasKovacs•

It's not horribly bad. The whole point of ST is to allow writing mutating algorithms behind pure interfaces. At the end of the day, when we write library code, we produce value for our users, and if our ST implementation is 5x faster than the immutable implementation, this should be seriously considered. The tradeoff is that our implementation will be uglier (which isn't set in stone, and partially Haskell's fault) and possibly (but not certainly) harder to understand for potential contributors, and would be less amenable to formal verification. These trade-offs should be weighted proportionally, and not dismissed based on some abstract ideological disposition.

A great joy of many FP abstractions is that internals can be truly hidden, without any leaks. This gives us freedom that should be appreciated. It is absolutely not an essential feature of functional programming that implementation details use immutable data structures. Immutability has many advantages, but it's only a means to get what we ultimately care about, namely strong guarantees, abstraction, flexibility, performance, etc.

I have written a great deal of very low level Haskell, and it looks like very ugly C code, with just slightly more guarantees than C. But this is not the way it must eternally be. I think that in a future dependently typed language it would be feasible to implement primitive operations as a strongly typed EDSL inside the language, with memory layout and field sizes reflected in the type system.

That's the real power of types: that whenever we have a problem that have to be solved and cannot be worked around, we can formalize it and abstract over it in a machine checked way, no matter how messy it is. In Haskell it's best practice to stick to domains where Haskell's type system is strong enough to provide reasonable guarantees. In many domains Haskell is too weak for that. This is a fact about Haskell, not about domains.

8
dramforever•

You are trying to use a functional language imperatively.

By that I mean that if you want this:

It's a bit hard to convince friends that Haskell is a good language for writing imperative code when it takes four lines to write the equivalent of [...]

You probably shouldn't be using Haskell like that :P

1