I heard Facebook tried to adopt this language...

Posted by Dillon Reedy on 2017-02-28

but Mark Zuckerberg Haskelled it?

Prerequisites

So let’s get started with the basics of what we’re going to need.

  1. We’re gonna need our Haskell compiler GHC
  2. Create a file in some directory where you’d like to keep your Haskell project
  3. Navigate to that directory in cmd prompt, and execute the commands “cabal updates” and “cabal install matrix” this is essentially some packages that we are going to need.
  4. Inside of this directory also get a clone of ddrakes Haskell Dijkstra repository using the command “git clone https://github.com/ddrake/haskell-dijkstra“ (thank you u/ddrake)

An R Program to Create our Input

If you don’t want to go through this process to create an R program to create our inputs, then I created a Google spreadsheet that contains input data. That you can copy into a .txt file of our directory.

If you’d like to use my R program that I made it’s a simple script that will make you a nice little contour map, and then write to a .txt file your inputs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
setwd("<Your working directory path>")
install.packages('Rcpp', dependencies = TRUE)
install.packages('ggplot2', dependencies = TRUE)
install.packages('plotly', dependencies = TRUE)
install.packages('DBI', dependencies = TRUE)
install.packages('webshot', dependencies = TRUE)
library("DBI")
library("ggplot2")
library("plotly")
library("webshot")
x2 <- 1:10
y2 <- 1:10
# Height tests number 1
#/*z2 <- matrix(expand.grid(x2,y2)$Var1^2 + expand.grid(x2,y2)$Var2^2,10,10)*/
# Height tests number 2
z2 <- matrix(sample(1:50, 100, replace=T),10,10)
p <- plot_ly(x = x2, y = y2, z = z2, type = "contour")
webshot::install_phantomjs()
tmpFile <- tempfile(fileext = ".png")
export(p, file = tmpFile)
browseURL(tmpFile)
write.table(z2, file="input10x10.txt", row.names=FALSE, col.names=FALSE)

With all these prerequisites finally made we can start discussing some Haskell!

Haskell Stuff

Haskell is something that I’ve been working in for years, I originally got into this language because in college we were studying functional programming and this language got briefly mentioned. One day I may come back to this language to implement a game or something (who knows).

I would later go on to start using Haskell for programming competitions because I liked the ability to do a lot with a little code. It was a time saver from that perspective. I’ve solved competition problems that would normally take like 100 lines of code in 1 or 2 lines. I even gave a lecture on the subject (it used a lot of Ryan Gosling memes) and I wouldn’t try it again.

Without further adieu, let’s describe out the problem we are solving.

Problem Statement

So originally I wanted to solve the nifty problem of navigating through a mountainous region such that we take a path that has the least elevation change. I loosened the solution further and further due to time constraints, and I eventually just settled upon “get us the minimum cost to navigate from the Eastern edge of the map to the Western edge of the map”. This is partly due to Haskell not being great at solving this solution (although it totally can). It’s just not the best for it.

Haskell Code

Let’s analyze some bits and pieces of my program that were crucial to solving this issue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
main = do
print "What is the file name?"
fileName <- getLine
contents <- readFile (fileName ++ ".txt")
-- Input re formatting
let inputLis = map readInt . words $ contents
rows = inputLis !! 0
cols = inputLis !! 1
inputTable = drop 2 inputLis
inputMatrix = (fromList rows cols inputTable)
outputStr = (concat (getStrLis (getAllEdgesAndCosts inputMatrix rows cols)))
g = fromText outputStr True
allSolns = (getAllSolns (getStartingPts inputMatrix) g)
minToEnd = (getMinimumDistance (getEndingPts inputMatrix) allSolns)
print minToEnd

Our input is in the form of a matrix that is the heights of the mountainous region. So we’re gonna have to change this to be able to use Dijkstra upon it. What we need is a list of “<Start Node> <End Node> <Edge Cost>”. So I suppose the first function we should analyze to be able to get such input would be the getAllEdgesAndCosts function.

getAllEdgesAndCosts

So the getAllEdgeCosts function just appears to be moving input into its’ tick function (A tick function being a function named exactly the same as its’ calling function but with a tick at the end of it.)

A list comprehension is used in the getAdjacencyList function to get all the points on the matrix. This will result in a list of tuples numbered as such [(1,1), (1,2), (1,3)..]. The getAdjacencyList function will then filter out points that go outside the matrix, and points that try to refer to itself (because we don’t want to move to the same location when walking along a path!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-- This function will return back a list of tuples that are formatted as follows:
-- [(startPt, endPt1, edgeCost1), (startPt, endPt2, edgeCost2)..]
getEdgeCosts _ _ _ [] = []
getEdgeCosts givenHeightMatrix givenNameMatrix startPt (endPt:endPts) =
((givenNameMatrix ! startPt),
(givenNameMatrix ! endPt),
(getEdgeCost givenHeightMatrix startPt endPt)) :
(getEdgeCosts givenHeightMatrix givenNameMatrix startPt endPts)
getAllEdgesAndCosts` givenHeightMatrix maxX maxY =
getAllEdgeCosts` givenHeightMatrix
(fromList maxX maxY [1..])
(getAdjacencyList [(i, j) | i <- [1..maxX],
j <- [1..maxY]] maxX maxY)
getAllEdgesAndCosts givenHeightMatrix maxX maxY =
concat (getAllEdgesAndCosts` givenHeightMatrix maxX maxY)

The getEdgeCosts function uses a nice feature of Haskells called “wildcards”. Wildcards are used essentially for parameter inputs that we don’t care about. The only parameter input we care about for getEdgeCosts is the list of endPoints, and when the list of endPoints has run out.

We then use a nice Data.Matrix feature to access an element, we use the single exclamation point. So essentially it is “<Given Data.Matrix> ! <Tuple of matrix element you’d like to access (essentially a point on the matrix)>

The getEdgeCost function will just get the absolute value of the difference between the heights.

getAllSolns

This function is pretty straight forward once we have all the starting locations. In which I use a neat little math feature in Haskell to get all the starting locations:

1
2
3
4
5
6
7
8
9
10
11
12
13
-- A function that given a matrix, returns back a
-- vector that contains all the possible starting points
getStartingPts` numRows numCols =
take numRows [1,(1+numCols)..]
getStartingPts givenMatrix =
(getStartingPts` (nrows givenMatrix) (ncols givenMatrix))
-- Given the list of starting points, we get the Dijkstra scores of all the
getAllSolns [] _ = []
getAllSolns (startingPt:startingPts) g =
(dijkstra g (show startingPt)):(getAllSolns startingPts g)

I personally love how Haskell can predict to fill out the list in the given math function style, for as much as I need to populate the list for. It’s such a nifty feature in my opninion. Arguably one of my favorite features.

The Dijkstra function was provided by ddrake on his Github, if you have not taken a look at that repository you should to get an idea of what is going there.

The final function getMinimumDistance is a pretty straight forward idea, that you should look at my Github to figure out what is going on, but the basic idea is to iterate through all the start locations, get their Dijkstra graphs, and then iterate through the end locations on the Dijkstra graph keeping a running minimum value.

Dear Haskell,

I love you, but I get why people don’t love you. There’s not a lot I can do with you, I can see why people like to use you as a server side language, but outside of that what are your uses? It makes it hard to love you. When we reach the day when I can do a lot with you, I’ll come back, but as for now I’ll just keep trucking along.