Thread by @GabriellaG439

I've been trying to write a blog post explaining the difference between functional and imperative programming and I've failed multiple times due to writer's block

Instead, I'm going to dump my thoughts here on a Twitter thread to finally get this out of my head 🧵 (1/16)

Okay, so the difference is:

Imperative programming is a style that predominantly uses linear programs and linear data structures

Functional programming is a style that predominantly uses tree-like programs and tree-like data structures

I'll explain …

Linear data structure = lists

Linear programs = statements

Tree-like data structure = algebraic data type

Tree-like program = expression

A linear data structure is basically a sequence of 0 or more elements. For example:

[ 2, 3, 5 ]

Imperative programs tend to overemphasize arrays/lists/vectors compared to their functional counterparts

A linear program is a sequence of 0 or more statements. For example:

main = do
putStrLn "Enter your name:"
name <- getLine
putStrLn name

Imperative programs tend to overemphasize organizing code around statements

A tree-like data structure is an algebraic data type that permits arbitrary branching and nesting

A more mainstream example is JSON

A less mainstream example is an abstract syntax tree (literally a tree-like data structure)

Functional programs tend to prefer tree-like data

A tree-like program is an expression, which permits arbitrary branching and nesting

For example, this expression is branched and nested, with each operator corresponding to a node in the syntax tree:

(x < y - 1) || (y + 1 < x)

Functional programs tend to prefer expressions

It's not an accident that control flow parallels data structures

If you overemphasize linear data structures then you need to overemphasize linear control flow (e.g. for loops or while loops) in order to process them

Similarly, tree-like data works better with tree-like code

For example, this is why functional languages and programming styles tend to be overrepresented in compilers

It's easier to manipulate abstract syntax trees if your language is ergonomically optimized for tree-like computation (expression-oriented programming)

This post of mine goes into more detail about the correspondence between data structures and control flow a bit more in the context of functional programming: haskellforall.com/2021/02/folds-…

A classic example of the imperative/functional dichotomy is Docker vs Nix

A Docker file is predominantly a linear sequence of build instructions

A Nix derivation is predominantly a tree representing the dependency graph

Docker = more imperative
Nix = more functional

I say "predominantly" because Dockerfiles can now have multiple FROM statements (which makes them more functional) and Nix builds can locally run shell commands (which makes them more imperative), but you get the idea

Functional or imperative programming is not necessarily inherent to a programming language or tool. You can write functional code or imperative code in, say, JavaScript

That said, one style tends to dominate in most programming language communities

One example is Go vs. Haskell

Go is mildly hostile towards algebraic data types and expression-oriented programming, and Go is widely regarded as imperative

Haskell is mildly hostile to statements and arrays and Haskell is widely regarded as functional

You can program in a functional style in Go, but you'd be going against the grain (both the language and the community)

Vice versa, you can program in an imperative style in Haskell, but you'd also be going against the grain

I'm not the first person to explain functional programming in this way. This way of explaining things dates back at least to Landin's "The Next 700 Programming Languages": cs.cmu.edu/~crary/819-f09… (16/16)