Type Driven Development: Simple masonry layout in 50 lines of Elm code

Demo: http://elm-masonry.surge.sh/

Code: https://github.com/lucamug/elm-masonry/

Code in the browser: https://ellie-app.com/8j8XdXn7xHda1

The final result:

A Masonry layout is a way to fit together elements of possibly different sizes without gaps.

There are many different way to implement masonry layout, using CSS and/or Javascript. It is a kind of bin packing problem.

The method that we will use in this tutorial is simple. Adding elements from left to right in a set of columns. Each element is added in the column that has shorter height.

We will talk a lot about fold (or reduce in other languages). So have a look at their definition before keep reading.

We will also let the types of our functions to drive our development in an attempt of what is called Type Driven Development.

Let’s start digging in the code!

We want to transform a list of heights into a two dimensional matrix that represent the columns of the final layout:

So from this data:

items = [ 250, 200, 300, 200, 450, 200, 300, 500, 300, 250, 200, 150, 200 ]
columns = 4

to this matrix:

[ [ (11, 150 ), ( 8, 300 ), ( 5, 200 ), ( 3, 200 ) ]    X
, [                         ( 7, 500 ), ( 2, 300 ) ]    ^
, [             (10, 200 ), ( 4, 450 ), ( 1, 200 ) ]    │
, [ (12, 200 ), ( 9, 250 ), ( 6, 300 ), ( 0, 250 ) ]    │
]                                                       │
                                          Y <───────────┼

That will show up flipped on screen:

╔════════════════════════════════════════════════════╗
║ (  0, 250 )  (  1, 200 )  (  2, 300 )  (  3, 200 ) ║
║ (  6, 300 )  (  4, 450 )  (  7, 500 )  (  5, 200 ) ║
║ (  9, 250 )  ( 10, 200 )               (  8, 300 ) ║
║ ( 12, 200 )                            ( 11, 150 ) ║
╚════════════════════════════════════════════════════╝

the first value of the tuples in the matrix is the position in the initial list, the second is the height.

Note that the matrix is filled from the bottom right with element 0 and that rows in the matrix will be columns in the layout.

The idea is that each item will be added to the matrix row that has a smaller value, where the value is the sum of all items already present in the row.

This is a progression of the matrix creation:

The first four items are added to each row because the sum is equal zero:

[ [               ( 3, 200 ) ]
, [               ( 2, 300 ) ]
, [               ( 1, 200 ) ]
, [               ( 0, 250 ) ]
]

The fifth item will go in the second row from bottom because it sum is the lower (200), together with the fourth row.

[ [               ( 3, 200 ) ]
, [               ( 2, 300 ) ]
, [   ( 4, 450 ), ( 1, 200 ) ]
, [               ( 0, 250 ) ]
]

The fourth row is the next to be occupied

[ [   ( 5, 200 ), ( 3, 200 ) ]
, [               ( 2, 300 ) ]
, [   ( 4, 450 ), ( 1, 200 ) ]
, [               ( 0, 250 ) ]
]

Now the row with the minimum sum is the second (250):

[ [   ( 5, 200 ), ( 3, 200 ) ]
, [               ( 2, 300 ) ]
, [   ( 4, 450 ), ( 1, 200 ) ]
, [   ( 6, 300 ), ( 0, 250 ) ]
]

…and so one until all the items are included.

As a starter let’s define some alias of types so that type signature would be meaningful.

type alias Position =
    Int

type alias Height =
    Int

type alias Masonry =
    List (List ( Position, Height ))

Nothing new here. Let’s plan the algorithm only using type signatures.
The end result is a function that given a list of heights and a number of columns would return a Masonry. Let’s call it fromItems:

fromItems : List Height -> Int -> Masonry

Because we need to keep track of the position of the Heights, List.Extra.indexedFoldl seems a good candidate for this job.
The type signature of indexedFoldl is

indexedFoldl : (Int -> a -> b -> b) -> b -> List a -> b

putting these two signatures together we obtain:

a = Height

b = Masonry

so indexedFoldl became

indexedFoldl : (Int -> Height -> Masonry -> Masonry) -> Masonry -> List Height -> Masonry

we need now an helper function of the type

Int -> a -> b -> b

equivalent to

Position -> Height -> Masonry -> Masonry

this function add the Item (Position, Height) to the Masonry so let’s call it addItemToMasonry.

It will be called for every Item so the Masonry will grow gradually the way we explained at the beginning of he post.

Before adding an Item we need to find the column with smallest height.

We need a function with this type signature:

Masonry -> Position

Let’s call this function minimumHeightPosition and let’s split this function in two smaller functions with these type signature:

Masonry -> List Height

List Height -> Position

The first function transforms a Masonry in a list of heights, one height per column (columnsHeights)

The second function loops on this list and return the position of the smallest column, using the already used indexedFoldl (positionOfShortestHeight)

Done! This is the simple outcome of the script:

You can find the final code at https://github.com/lucamug/elm-masonry/blob/master/src/Masonry.elm

Code in the browser: https://ellie-app.com/8j8XdXn7xHda1

This is a simple result: http://elm-masonry.surge.sh/simple.html

This is a demo that showcases the possibilities of the masonry script: http://elm-masonry.surge.sh/

This post was originally posted in Medium.