DEV Community: thealmarty

Recursion: An Indispensable Tool For Every Functional Programmer [Example With Insertion Sort]

thealmarty — Tue, 13 Apr 2021 15:35:21 +0000

This is the first of a series of articles that illustrates functional programming (FP) concepts to imperative programmers. As you go through these articles with code examples in Haskell (one of the most popular FP languages), you gain the grounding for picking up any FP languages quickly. Why should you care about FP? See this post.

One of the most important concepts is the use of recursion in place of loops. Loops are an important tool for imperative programmer to perform repeated actions. Functional programmers use recursion (calling the function itself) instead. Below, I use the insertion sort algorithm as an example. I first implement it in imperative style, then I implement it in functional style in Haskell.

Insertion Sort

I’ve chosen insertion sort as an example algorithm to illustrate how loops and recursion serve similar purposes. Of course, many languages have a sorting algorithm built-in, so most of the time you don’t need to write your own.

The insertion sort algorithm can be described as: separate the given list of elements into two list: one sorted, one unsorted. The sorted list initially contains the first element of the given list while the unsorted list initially contains the rest of the elements. In each step, take the first element from the unsorted list, compare it with each element of the sorted list, starting from the right most (or left most) element. Insert the element right after the element it should follow.

Imperative style implementation

Below is the pseudocode from Wikipedia. See also the C, C++, and OCaml implementation. Don’t worry about understanding the code line by line, the main point is that we use two loops for the algorithm.

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

You can see that insertion_sort is a function that takes an array A and sorts it in place , that is, it rearranges the elements in A as the function runs. When you run insertion_sort with array A, A becomes the sorted array, this is not the case in FP.

Recursion

Instead of using loops for repeated actions, FPers use recursion. A recursive function calls itself as part of its own function definition! It’s common to recurse on the tail of a list. The tail is the whole list without the first element (the head). Like loops, recursion requires a terminating condition. Because the tail is guaranteed to have one fewer element than the original input, we know that as it recurses its input is smaller and thus it can terminate.

Functional style implementation in Haskell

The Haskell implementation includes recursive functions sort and insert :

sort :: Ord a => [a] -> [a]
sort l = sortInto [] l -- initially all elements are unsorted
  where
    sortInto :: Ord a => [a] -> [a] -> [a]
    sortInto sorted [] = sorted
    sortInto sorted (l:ls) = sortInto (insert sorted l) ls

    insert :: Ord a => [a] -> a -> [a]
    insert [] elem = [elem]
    insert sorted@(s:ss) elem | elem > s = s : insert ss elem
                              | otherwise = elem : sorted

egL :: [Int]
egL = [23,2,5]
main = putStrLn $ show (sort egL) ++ show egL

The function sort is declared with its types first. sort is a function that concerns a type a that can be ordered (hence Ord a before =>). sort takes a list with elements of type a and returns a list with elements of type a. That is, instead of sorting the list in place, sort returns a new list! sort calls sortInto to perform the function of in the outer loop in the imperative implementation.

Inside sort we also define insert, which performs the function of the inner loop in the imperative implementation. But instead of calling each element by position like the while loop, insert is a function that takes two arguments, a sorted list, sorted and an element that is to be inserted in the correct position, elem. The function compares the element with the sorted list head, s, and the rest of the sorted list, ss, is passed to the recursive call to continue with the next comparison. The recursion terminates when either

elem is not greater than the next element of the sorted list, and is inserted in front of that element. Or – elem is being inserted at the end of the list. The first pattern match case. The resulting list of this call contains the single element elem.

sortInto is also a recursive function defined inside sort. It takes as arguments a sorted list, and an unsorted list. Since sorted is a sorted list, we can put it in as an input to insert so that insert can insert the first element l of the unsorted list properly. sortInto then recursively calls itself to insert the rest of the elements of the unsorted list in to the sorted list returned by insert.

sort calls sortInto with an empty sorted list, and the whole unsorted list as the unsorted list.

Save the above code in a file named main.hs. After you install GHC, you can run it in a terminal:

> runhaskell main.hs
[2,5,23][23,2,5]

You can see that after running sort egL, egL stays unchanged. That is, FP preserves the inputs.

In this post, you’ve learned quite a few important concepts! We’re more aware of types , we learned that a function takes an input and gives an output (instead of performing actions in place), and we learned recursion. In the next post, I will show a glimpse of the power of FP with higher order functions, which gives the FPer tremendous expressive powers and enables many awesome and concise ways to describe algorithms. For example, recursion schemes , which let you describe recursion in a single line of code.

The post Recursion: An Indispensable Tool For Every Functional Programmer [Example With Insertion Sort] appeared first on The Always Learning Marty.

Why you should learn functional programming

thealmarty — Wed, 10 Mar 2021 22:06:52 +0000

Many of the widely used languages (including C++, Java, and Javascript) are imperative. In imperative programming, computations are structured as sequences of instructions that operate by making modifications to the state of the program. Functional languages operate by declaring functions. The output value of a function depends only on the arguments that are passed to the function. Because of this, functional languages have a few advantages that minimize mistakes.

“Sometimes, the elegant implementation is a function.

Not a method. Not a class. Not a framework. Just a function.”

–John Carmack

Until recently, functional languages were considered “academic” and for research only. But the industry has since discovered their advantages and many leaders are adopting functional programming to gain competitiveness.

In this post, I’ll list a few reasons why you should learn functional programming.

It makes you a better programmer

Functional programming, especially typed functional programming, offers a very different mental toolbox than the traditional programmer usually uses. For example:

Immutability

Unlike in imperative languages, in functional languages, variables are immutable by default, and do not depend on the state of the program. Along with referencial transparency (given the same inputs, a function always return the same results), this increases consistency. As a result, we have reduced errors, increased stability, and increased effectiveness of tests. For example, tools like QuickCheck is very effective.

Type safety

Modern functional languages are usually statically typed, which means that they type check (verify all functions have the correct input types passed to them and return the correct type) at compile-time as opposed to run-time. This ensures that all program in production are type safe. Even though some imperative languages are also statically typed, they don’t offer as many safety guarantees as modern functional languages.

Memory safety

Functional programming languages handle allocation and de-allocation for you. The compiler avoids many common memory leaks that imperative programmers see and completely removes the risk of null dereferences.

Purity

In pure functional languages like Haskell, you can prove the absence of unwanted side-effects. Because pure functional languages operates with functions that are type safe, you can control whether a function in the code has any interaction with the outside world more easily.

And many more! See here and here for more details.

These new tools and perspectives empower you to write better programs even when you write in traditional languages. In fact, many modern languages/extensions/frameworks have functional flavours added. See for example Rust, ReasonML and typescript. Learning functional programming will give you the necessary building blocks to pick up these framework quickly and correctly.

It’s enjoyable

A far smaller cognitive load is required when writing functional rather than imperative code. As mentioned above, in functional programming the compiler type checks and ensures memory safety. In additional, functions have no side effects. Therefore, many concerns present in imperative languages can be completely offloaded to the compiler. With this tedious cognitive load freed up, functional programmer can focus on the more fun part of programming: designing the implementation! When we develop in functional languages we often write much less code, in substantially less time, and with fewer bugs.

It gives you great career prospects

Many companies have adopted functional programming and there are many opportunities for functional programmers. Companies using Haskell include Facebook, Hasura, etc. Companies using OCaml include Ahrefs, Jane Street, etc. Check out Functional Works for many more companies that are using functional languages!

Functional languages are prominent in blockchain especially. Blockchain is an increasing popular technology with applications in many areas. The most common uses of the technology include cryptocurrencies, banking/FinTech, and smart contracts. They all involve financial transactions that are time sensitive and mistakes can be very costly. Functional languages can minimize these mistakes and therefore many blockchain and related applications are written in functional languages! For example, Mina and Tezos are written in OCaml. Cardano, Kadena and BlockApps are written in Haskell.

Check out Blockchain Works for many more blockchain related companies that are using functional languages!

In conclusion, functional languages have advantages over imperative languages. They are already well-used in the blockchain world, and are really catching on in other areas as well. Whether you want to stay up-to-date, expand your career choices, or broaden your programming knowledge, learning functional programming is the ideal choice!

If I’ve got you convinced, I’ve got more good news for you! I’m going to publish a series of posts introducing functional programming concepts. You don’t need to have background in functional programming or even programming. I’ll go through practical concepts from beginner to advanced levels with many code examples. Stay tuned!

The post Why you should learn functional programming appeared first on The Always Learning Marty.