CODEWITHSUNDEEP
functional-programming
Zen
Zen

Reputation: 5490

What does it mean that functional languages provide explicit data structure representations?

I'm read chapter 1.13 AN INTRODUCTION TO FUNCTIONAL PROGRAMMING THROUGH LAMBDA CALCULUS and see it. What is the "explicit data structure representations" that is usually absent in imperative languages? Could anybody give an example please?

Upvotes: 1

Views: 50

Answers (1)

Mulan
Mulan

Reputation: 135187

Could anybody give an example please?

This is just an example of implicit structure, Array, compared to explicit structure, Linked List.

The programs below could be written in countless ways. Neither example is particularly amazing. Each example is just meant to show code you could expect to see in the wild.

Overview

An Array is a non-explicit, nebulous bucket of index->value mappings. It requires the use of an arbitrary index input to read a value. You can "iterate" thru it by using a counter, but really the counter has no relation to the array itself – you're still just performing random lookups using an arbitrary index – it doesn't matter if those happen to be in "sequence" or not.

enter image description here

A Linked List is an explicitly structured data container. It has a defined beginning, end, and meaningful way to programmatically interact with the structure. Processing the list starts with car and proceeds using cdr until the null terminator is found. It also has explicit ways to create new pairs (cons).

enter image description here

Non-explicit code example

Here we have an imperative-style program written in JavaScript. There is arguably no structure to this program.

  • xs is a globally-defined array that is essentially a large blob of assignments – values linked to indices
  • doSomething changes an assignment based on the provided index – it does so implicitly on xs
  • main also has implicit knowledge of xs – or at least, it has implicit knowledge that doSomething operates on xs
  • also notice that because doSomething only sets a new assignment of a known index, it mutates the original input
  • main has no explicit output; it implicitly relies upon doSomething to change the underlying data, xs

function doSomething (i) {
  xs[i] = 'changed'
}

function main () {
  doSomething(1)
  doSomething(2)
}

let xs = ['a', 'b', 'c', 'd', 'e']

console.log(xs)       // [ 'a', 'b', 'c', 'd', 'e' ]

console.log(main())   // undefined

console.log(xs)       // [ 'a', 'changed', 'changed', 'd', 'e' ]

Explicit code example

Here is a functional-style program written in Racket.

  • xs is still globally-defined but it is in a known, explicit structure – a Linked List
  • doSomething can no longer reference an index directly to reassign a value. Instead, it requires both an index input and an explicitly structured list input – only then can recursively build a new list with the new value in the appropriate position.
  • main can no longer maintain ignorance of the data it operates on – xs is explicitly and purposefully threaded thru successive doSomething calls, using the return value of each, and ultimately returning the final result
#lang racket

(define (do-something i xs)
  (if (zero? i)
      (cons "changed" xs)
      (cons (car xs) (do-something (sub1 i) (cdr xs)))))

(define (main xs)
  (do-something 2 (do-something 1 xs)))

(define xs '(a b c d e))

(println xs)         ;; => '(a b c d e)

(println (main xs))  ;; => '(a "changed" "changed" d e)

(println xs)         ;; => '(a b c d e)

Upvotes: 1

Related Questions