---
title: Linked List Operations
date: "2019-06-08"
series:
  - programming
  - functional programming
  - elixir
  - haskell
  - ocaml
  - reasonml
---

I like [linked lists](https://en.wikipedia.org/wiki/Linked_list).
They are _super_ simple data structures and are really fun to implement!
Whenever I pick up a language I think writing a linked list module is a great way to learn lots about a languge.
You can do lots of different operations on a list and functional languages tend to create really simple ways of implementing a linked list.
The `fold`/`reduce` function is also a super powerful tool to many other implement utility functions on a recursive data structure like a linked list as well!

Here, I'm going to implement a tiny linked list library containing a
`head`, `tail`, `fold`, `map`, and `length` function in
[Haskell](#haskell)[^1], [ReasonML](#reasonml)[^2], [OCaml](#ocaml)[^3], [Elixir](#elixir)[^4], and [F#](#f)[^5].

### Haskell

```haskell
module LinkedList where

data LinkedList a = Node a (LinkedList a) | Nil

llHead :: LinkedList a -> a
llHead (Node a _) = a

llTail :: LinkedList a -> LinkedList a
llTail Nil = Nil
llTail (Node _ a) = a

llFold :: b -> (b -> a -> b) -> LinkedList a -> b
llFold acc _ Nil = acc
llFold acc f (Node x xs) = llFold (f acc x) f xs

llMap :: (a -> b) -> LinkedList a -> LinkedList b
llMap f Nil = Nil
llMap f (Node x xs) = Node (f x) (llMap f xs)

llLength :: LinkedList a -> Int
llLength Nil = 0
llLength xs = llFold 0 (\a _ -> succ a) xs
```

### ReasonML

```reason
module LinkedList = {
  type t('a) =
    | Nil
    | Node('a, t('a));

  let head =
    fun
    | Nil => Nil
    | Node(x, _) => x;

  let tail =
    fun
    | Nil => Nil
    | Node(_, xs) => xs;

  let rec fold = (acc: 'a, f: ('a, 'b) => 'a, l: t('b)): 'a =>
    switch (l) {
    | Nil => acc
    | Node(x, xs) => fold(f(acc, x), f, xs)
    };

  let rec map = (f: ('a) => 'b, l: t('a)): t('b) =>
    switch (l) {
      | Nil => Nil
      | Node(x, xs) => Node(f(x), map(f, xs))
    }

  let length = l => fold(0, (a, _) => a + 1, l);
};
```

### OCaml

```ocaml
module LinkedList =
  struct
    type 'a t =
      | Nil
      | Node of 'a* 'a t

    let head = function
      | Nil -> Nil
      | Node (node, _) -> node

    let tail = function
      | Nil -> Nil
      | Node (_, list) -> list

    let rec fold (acc : 'a) (f : 'a -> 'b -> 'a) (l : 'b t) : 'a =
      match l with
      | Nil -> acc
      | Node (x, xs) -> fold (f acc x) f xs

    let rec map (f : 'a -> 'b) (l : 'a t) : 'b t =
      match l with
      | Nil -> Nil
      | Node (x, xs) -> Node ((f x), (map f xs))

    let length = fold 0 (fun a _ -> a + 1)
  end
```

### Elixir

```elixir
defmodule LinkedList do
  defstruct [:value, :next]

  def head(%LinkedList{value: nil, next: nil} = ll), do: ll
  def head(%LinkedList{value: value}), do: value

  def tail(%LinkedList{value: nil, next: nil} = ll), do: ll
  def tail(%LinkedList{next: next}), do: next

  def fold(%LinkedList{value: nil, next: nil}, _fun), do: %LinkedList{value: nil, next: nil}
  def fold(%LinkedList{value: value, next: %LinkedList{value: nil, next: nil}}, _fun), do: value

  def fold(%LinkedList{value: value, next: next}, fun) do
    fold(next, value, fun)
  end

  def fold(%LinkedList{value: nil, next: nil}, initial_value, _fun) do
    initial_value
  end

  def fold(%LinkedList{value: value, next: next}, initial_value, fun) do
    fold(next, fun.(initial_value, value), fun)
  end

  def length(%LinkedList{value: nil, next: nil}), do: 0
  def length(%LinkedList{next: next}), do: 1 + LinkedList.length(next)

  def map(%LinkedList{value: nil, next: nil}, _fun), do: %LinkedList{value: nil, next: nil}

  def map(%LinkedList{value: value, next: next}, fun) do
    %LinkedList{value: fun.(value), nex: map(next, fun)}
  end
end
```

### F&#35;

```fsharp
module LinkedList =
    type LinkedList<'a> =
    | Nil
    | Node of 'a * LinkedList<'a>

    let head =
        function
        | Nil -> Nil
        | Node(x, _) -> x

    let tail =
        function
        | Nil -> Nil
        | Node(_, xs) -> xs

    let rec fold acc f l =
        match l with
        | Nil -> acc
        | Node(x, xs) -> fold (f acc x) f xs

    let rec map f l =
        match l with
        | Nil -> Nil
        | Node(x, xs) -> Node((f x), (map f xs))

    let length l = fold 0 (fun a _ -> a + 1) l
```

Language features like currying, pattern matching, and type-safety are super nice when doing exercises like this.
When I began to write this post I challenged myself to try it out in Haskell to learn some of the language, so it
was a very fun task to actually dig into some Haskell syntax to figure out how to do it all.

A fun observation I noticed is that most of these languages all pretty much look like one another.
I my first linked list module was written in JavaScript some years ago, where I then converted it into Elixir[^6], but with many more functions.
Once I had that knowledge as baseline, I was able to convert it to all of these other functional languages with relative ease.
After looking at and writing in these languages I would have to say Haskell is probably my favorite to think in while writing.
The type syntax is great and the language as a whole is super minimal, which is great for any language, in my opinion!

I highly encourage you all to try out some of these languages and write a program or two!

[^1]: https://www.haskell.org/
[^2]: https://reasonml.github.io/
[^3]: https://ocaml.org/
[^4]: https://elixir-lang.org/
[^5]: https://fsharp.org/
[^6]: https://github.com/sean-clayton/linked-list/


Linked List Operations

---
title: Map and Reduce Arrays in JavaScript
date: "2017-06-10"
series:
  - javascript
  - programming
  - functional programming
---

[`Array.prototype.map`][0] and [`Array.prototype.reduce`][1] are some of the most _powerful_ array methods in JavaScript. Both serve similar purposes: Create a _new_ value from an array of values. But, what makes them awesome are also what make them different from each other.

[0]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map
[1]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce



### Map

The `map` method is purpose-built for creating a **new array** from an array. For example:

```tsx
const arr1 = [1, 2, 3, 4];
const arr2 = arr1.map((x) => x * 2);

console.log(arr2); // [2, 4, 6, 8]
```

This is fine and dandy, but in the real world we’re probably working with arrays of objects. Let’s say we have an array of friend objects that each have a name (string) and age (number). We want to just get an array of ages back. Map to the rescue!

```tsx
const friends = [
  { name: "Sean", age: 23 },
  { name: "Bob the Builder", age: 23 },
];

const ages = friends.map((friend) => friend.age); // [23, 23]
```

We can even use it with [React.js](https://facebook.github.io/react)!

```tsx {3-7,9}
const FriendList = () => (
  <ul>
    {friends.map((friend, i) => (
      <li key={i}>
        {friend.name}, {friend.age}
      </li>
    ))}{" "}
    {/* Equivalent to... */}
    {[<li key={0}>Sean, 23</li>, <li key={1}>Bob the Builder, 23</li>]}
  </ul>
);
```

Map is a really neat way with taking an array of items and returning a new array of items. If you want to take an array of items and return _any_ kind of value (array, number, object, etc), you'll want to use another array method...

### Reduce

The `reduce` array method is for creating a **new thing** from an array. If you have an array of objects and it should return a single number, `Array.prototype.reduce` is a tool for the job. Let’s use the `ages` array we mentioned in the Map example above:

```tsx
const sumAges = ages.reduce(
  (accumulator, currentValue) => accumulator + currentValue,
  0
); // 46
```

Let’s break this down.

The `reduce` method takes _two_ arguments: A callback function to perform actions on the array and return a value, and an initial value (very important). Here’s the previous code refactored to be more obvious what piece is what:

```tsx
const callback = (accumulator, currentValue, _indexOfCurrent, _array) =>
  accumulator + currentValue;
const initialValue = 0;
const sumAges = ages.reduce(callback, initialValue);
```

You can see the callback function being passed a few values. It is important to understand that the `reduce` method is meant to “squish” all the values in an array into a single value. Yes, you can mimic the exact functionality of `map` with `reduce`, but that is sort of pointless, no? Why use reduce at all? Reduce _accumulates_ a single value by iterating over an array, performing some sort of computation, and returning a new value to accumulate onto. Rinse, repeat.

- `accumulator`: This is an important piece of the `reduce` puzzle. This represents a possible final value that you want returned from the `reduce` method. In the `sumAges` function above, we want a number returned. The accumulator will thus be a number. It could be 0, -100, or 1, but a number nonetheless.
- `currentValue`: While iterating over the array, you have access to a single value from the array (the value in which is currently in the iteration). You would most likely use this current value to create a new accumulated value.
- `currentIndex`: This is a non-negative number that represents the index of `currentValue` in the array you’re working with.
- `array`: This is the array you are working with. I’ve hardly used it before, but I it can be handy for writing pure functions. I’m _guessing_ this is the array you are working with as it was in memory when you first called `reduce` on it. I haven’t tested that theory, though.

I can hear you asking now: “Well Sean, what is the first value for `accumulator`?” I’m glad you asked, observant person. Before we mentioned the `initialValue` argument, and that does _exactly_ this. Let’s look again at the `sumAges` code from above:

```tsx
const callback = (accumulator, currentValue, _indexOfCurrent, _array) =>
  accumulator + currentValue;
const initialValue = 0;
const sumAges = ages.reduce(callback, initialValue);
```

You notice that we made initial value `0`. If we didn’t do that, `initialValue` would be `undefined`. So when we look at the callback function, we can see a problem:

```tsx
(accumulator, currentValue, _indexOfCurrent, _array) => {
  // accumulator = undefined at this point!
  return accumulator + currentValue; // undefined + 23 = NaN
};

// sumAges = NaN now!
```

### Real-World

Let's say we're working with an array of objects that looks like this type definition:

```tsx
type PriceObject {
    subTotal: number,
    tax: number,
    discount?: number
}
```

You'll notice that `discount` is an _optional_ parameter in this object, so it could possibly be undefined. Reduce will make this work perfectly.
Let's work with an array of these `PriceObject`s to simulate a shopping cart of sorts, and each item could possibly have a `discount` parameter so we can show the user how much they're saving.

Here's what we want at the end of the day:

```tsx
type ShoppingCart = PriceObject[];

const shoppingCart: ShoppingCart = [
  {
    subTotal: 15.1,
    tax: 0.91,
  },
  {
    subTotal: 12.15,
    tax: 0.73,
    discount: 3,
  },
];

// Right here is where we want to implement reduce
// to combine (or *reduce*) the array into a single thing
const shoppingCartCombined = {
  subTotal: 27.25,
  tax: 1.64,
  discount: 3,
};
```

Now that we know what we want (a combined shopping cart object combining the parameters), we can solve it with reduce!

```tsx
const initialPriceObject: PriceObject = {
  subTotal: 0,
  tax: 0,
  discount: 0,
};

const shoppingCartCombined = shoppingCart.reduce(
  (acc, curr): PriceObject => ({
    subTotal: acc.subTotal + curr.subTotal,
    tax: acc.tax + curr.tax,
    discount:
      curr.discount === undefined ? acc.discount : acc.discount + curr.discount,
  }),
  initialPriceObject
);
```

Let's look at this. We intialize our `reduce` with an `initialPriceObject` which _ensures_ that we have all of our properties defined with an _initial value_ of `0`.
This is important later because it makes sure `acc` is an object with all our properties defined with a real value and not `undefined`.

In our `reduce` callback, we take the accumulated value and current value, and return an object that will always return an object with all properties of `PriceObject` defined with at least a `0`. If we wanted to display this on a UI, we can just check if `shoppingCartCombined.discount !== 0` and that will always work because it will never be anything other than a number. We have this guaruntee because `discount: curr.discount === undefined ? acc.discount : acc.discount + curr.discount` accounts for an object where `discount` is not a defined property and just returns the accumulated value if it isn't, and a new value if it is.

### Conclusion

`map` and `reduce` are super powerful. As a developer, I'm happy that it operates in a functional style and is super predictable and testable because of that. They are incredibly useful tools that should be a part of every JavaScript developers toolbelt.

Map and Reduce Arrays in JavaScript

---
title: Adventuring Out
date: "2017-01-01"
series:
  - elixir
  - programming
  - functional programming
---

As a lot of people do ringing in the new year, I made a resolution: To learn and become competent in at least one new programming language that has nothing to do with JavaScript. I’ve dabbled in some languages over the years since learning JavaScript—[CoffeeScript], [Python], [Ruby], [F#], [PureScript], [OCaml], [Elm], and a few others, but never on the level of JavaScript.

[coffeescript]: http://coffeescript.org/
[python]: https://www.python.org/
[ruby]: https://www.ruby-lang.org/en/
[f#]: http://fsharp.org/
[purescript]: http://www.purescript.org/
[ocaml]: https://ocaml.org/
[elm]: http://elm-lang.org/



While I enjoy learning new syntaxes and “The right tool for the right job,” it’s hard to maintain a steady level of learning while being only on the front-end side of web development. Being in front-end means you only use one language and one environment (essentially): JavaScript and the browser. JavaScript is an awesome language and the browser is an awesome place to be right now, but they’re hindering my learning and my natural drive to [be the very best like no one ever was](https://youtu.be/JuYeHPFR3f0). It was time to learn and use a new language on my own that had nothing to deal with work.

### The Problem

#### TL;DR: I’m picky and it’s really hard to find the perfect language for me.

I’m picky. I like JavaScript not because it’s extremely abusable, but because you can program in multiple paradigms with it. You can write JS that’s [object-oriented][object-oriented] (for you Java folk 😉), [prototype-based], and in the regular-ol imperative style. You can come from many different languages and probably find that JS has some way of supporting your style.

[object-oriented]: https://developer.mozilla.org/en-US/docs/Learn/JavaScript/Objects/Object-oriented_JS
[prototype-based]: https://en.wikipedia.org/wiki/Prototype-based_programming

My favorite and preferred style of writing code is [functional]. I won’t go into detail on why, but the rules and regulations of most functional languages fit into my natural way of thinking (functions over classes, immutable data over mutable, pure functions over statefulness). JS is also a functional language, so I enjoyed writing functional code with it. I’m proud to say all the new JS code I’ve written (4800+ lines in a project at work alone) is 99.999% functional.

[functional]: https://en.wikipedia.org/wiki/Functional_programming

![](/images/fp-trend.png)

> Functional programming doesn’t even hold a candle to the popularity and mind-share of object-oriented programming

When thinking about what language to pick, I knew I wanted to learn a functional one. If it had a `class` keyword, I wasn't going to learn it. Unfortunately, functional programming largely died out in the 70s/80s and has yet to make a huge comeback. I also wanted a strong type system. It's a big thing I think JS lacks, but I can understand it makes it harder for new devs to get into it, so I can forgive JS for that. I also want the awesome ecosystem and vibrancy of JavaScript.

### CoffeeScript

After dabbling in a few languages I’ve learned what I liked about all of them and what makes them fun to write in. I like CoffeeScript mainly because of it’s unapologetically minimalistic syntax:

```coffeescript
addOne = (a) -> a + 1
```

Equivalent to this in JS:

```tsx
var addOne = function (a) {
  return a + 1;
};
```

But it’s really just sugar’d syntax around JS that compiles right down to regular ol’ JS. And I already know JS. NEXT!

### Ruby

Ruby is awesome simply because of the entirely ginormous ecosystem and developer friendliness. You’ll be hard-pressed to find a nicer language to write in. But, for how nice it is as a language, it lacks in performance. And it’s OO 👎.

### F&#35;

F# is a language made by Microsoft and is part of the .NET stack. It’s multi-paradigm, but largely focuses on functional programming. F# is also strongly typed, much like Java, but comes with type inference, meaning if you wrote `let a = 1`, it'll just assume that `a` is of type `int` (it gets its types from .NET). Oh, and it has the best operator ever in a programming language: The pipe:

```fsharp
// pipe operator
[1..100]
  |> List.sum
  |> printfn "sum=%d"
// The fact that you can create a 100 item array with
// the numbers 1 through 100 by just writing [1..100] is AMAZING
// no curly braces, semicolons or parentheses
let square x = x * x
let sq = square 42
// simple types in one line
type Person = {First:string; Last:string}
// complex types in a few lines
type Employee =
  | Worker of Person
  | Manager of Employee list
// type inference
let jdoe = {First="John";Last="Doe"} // jdoe is of type Person
let worker = Worker jdoe
```

Simply beautiful.

Unfortunately, writing in a functional style in F# is, while the most preferred, not enforced. I like that it accommodates programmers coming at it from multiple angles (it kinda has to because of .NET’s huge amount of C# developers), but I want to be forced to write functionally — I do not want an out. Boy do I like it’s type system, though. Mmmmm :)

### PureScript, OCaml, Elm, and Others

These languages are all similar functional languages. PureScript is [very much like][influenced] [Haskell][haskell]. It is a very young language, though.

[haskell]: https://www.haskell.org/
[influenced]: https://github.com/purescript/documentation/blob/master/language/Differences-from-Haskell.md

OCaml is the complete opposite. It’s kinda old (made in the mid 90s, OCaml is part of the ML family of languages, originally made back in the 70s). It also is bad at concurrency (one of the natural benefits of a functional language is concurrency out of the box, generally). [BuckleScript] is a crazy awesome project which will compile OCaml code to JavaScript that looks human-written. Combined with Facebook’s [ReasonML], you actually write React code that looks like it’s written by humans (by writing Reason code) :D

[bucklescript]: https://github.com/bloomberg/bucklescript
[reasonml]: https://reasonml.github.io/

Elm is a nice language, but is somehow made only for the web browser? It’s really nice to look at in my eyes and the type system is nice (don’t get me started on it’s [developer friendliness]), but for some reason the creator thought it would be best to make it a compile-to-js language dependent on a bundled runtime that only works in a browser environment (only good for making interfaces in the DOM). I’m not sure why this is, but I don’t think it will help me writing non-front-end code.

[developer friendliness]: http://elm-lang.org/blog/compiler-errors-for-humans

### What Language Should I Pick?

All of these languages have some cool things and check of many boxes I have, but none check them all, and most don’t have anything close to a developer mind-share. Reason + BuckleScript sounds awesome, but is so new it’s considered in a prototype stage. CoffeeScript is just JavaScript underneath and I don’t want to be stuck with V8 and Node (single-threaded…). Elm is front-end only. Ruby is still OO, and while F# has an amazing type system, it’s still not 100% functional. I thought I couldn’t find a language for me. All hope was lost. Sean sad.

### The Solution

I honestly have no idea how I heard about it, but I ended up finding a language. The earliest thing in my Google history I could dig up about it was [an article I read back in August](https://blog.gitmonitor.com/gitmonitor-on-elixir-92a87c7eb382).

The language is [Elixir](http://elixir-lang.org/).

### What I like About It

Elixir checks of most of the boxes I want in a language to learn.

- 100% Functional
- [Wonderful concurrency](http://www.unlimitednovelty.com/2009/01/cutting-edge-of-vm-design.html)
- Pipe operator
- Made for web development
- Beautiful syntax
- Amazing community
- Pipe operator
- Great editor support
- Great tooling
- Strong history (for an extremely young language)
- `|>`

That’s not to say it’s perfect, though.

### What's Missing

- Types 😿
- Ecosystem not quite as large as JavaScript and some other popular languages
- Deployment story is a bit different than most because of the BEAM VM. More on that later.

All of that being said, Elixir is pretty much the language I want to learn now. It’s a young language (written in 2011), but stands on the shoulders of giants. It was written by a Ruby on Rails core team member, and compiles down to the Erlang (written in 1986) VM (BEAM) bytecode, so it runs on it. And even though the ecosystem is young and there’s a noticeable lack of types, it’s not a deal-breaker for me. Elixir is still a great language and I look forward to learning it!

Oh, and about a month ago I wrote some Elixir just to get the hang of it and made a [GraphQL](http://graphql.org/) API with it. You can find that project [here](https://github.com/sean-clayton/graph_ql). I also started answering the Elixir questions on [Exercism.io](http://exercism.io/) and put them in a [Git repository here](https://github.com/sean-clayton/exercism-answers).

Til next time!

Series: functional-programming