<commit_before>Retake
=========================

Pragmatic data structure and algorithmic transformations for modern JavaScript apps.


## Installation
```
npm install --save retake
```

## Usage

- Node (6 or later)

```
let retake = require('retake')
```

- Browser (gzips to *~5k*)

```Javascript
// es6
<script src="./node_modules/retake/lib/retake.js"></script>

// transpiled
<script src="./node_modules/retake/lib/retake.es5.js"></script>

// minified
<script src="./node_modules/retake/lib/retake.es5.min.js"></script>

// retake...

```

- For es5 versions - use [Babel polyfill](https://babeljs.io/docs/usage/polyfill/)

```Javascript
<script src="https://cdnjs.cloudflare.com/ajax/libs/babel-polyfill/6.13.0/polyfill.min.js">
</script>
```


## Introduction

ECMAScript, the language, lacks built-in support for advanced data structures. 
Arrays and Objects in JavaScript are highly efficient and provide a flexible API. 
However their mutative surface area does not serve well in design of concurrent systems. 
This is especially true for web apps (React, Flux, Redux et al.) where UIs can be described as a function of application state in a constant fold of events. 
Use of functional data structures is key to achieve referential transparency in such scenarios.

ES2015 has introduced game-changing features (for e.g. generator functions, lambdas, iteration protocols, proper tail calls) that improve performance and offer great flexibility in representing computations. 
As a result, we've benefited from libraries such as Immutable.js and Mori that offer an assortment of fully persistent data structures.

Retake takes a more pragmatic, refined approach in managing *pieces of data* your app cares about *at any given time*.
It is comprised of List, Zipper, and Transforms that enable proper organization of data for efficient traversal and updates. 
These functional concepts are implemented and exposed in a way to meet requirements of modern JavaScript apps. 
The end goal is to free app domain of procedural code by isolating the overhead of persistence and retrieval.

This implementation covers 3 important facets:

  - Lazy List - provides an immutable persistent collection to organize data linearly using head/tail decomposition with lazy evaluation.
  - Transforms - provide an integrated way to compose and apply algorithmic transformations to data structures.
  - List Zipper - facilitates efficient traversal and updates to encompassing linear data structure.

That's very much the gist of it! Try code examples below.

By the way, it should be clear that list-based structures are primarily purposed for sequential access unlike Vectors that are index-based.

Helpful readings:
- [Persistent Data Structure](https://en.wikipedia.org/wiki/Persistent_data_structure)
- [Transducers](http://clojure.org/reference/transducers) by <NAME>
- [Zipper](https://en.wikipedia.org/wiki/Zipper_(data_structure)) by <NAME>


## Code Examples

### Look-and-say numbers

Watch this [video](https://youtu.be/ea7lJkEhytA?list=PLt5AfwLFPxWIL8XA1npoNAHseS-j1y-7V) by <NAME> for an introduction to this sequence.

Let's first implement a function that produces the "look and say" (next element in sequence).

### a. Using Transforms on List
```Javascript
function look_and_say(l, acc=empty) {
    if(l.done) return acc
    let focus = l.first, count = 0
    let split = l.splitWhen(v => !(focus === v && ++count))
    acc = acc.append(count, focus)
    return look_and_say(split.tail.first, acc)
}
```

### b. Using Zipper Transforms on List
```Javascript
function look_and_say_zipper(z) {
    z = z.unzip()
    if(z.focus === void(0)) return z.list.flatten()
    let focus = z.focus, count = 1
    while(focus === (z = z.unzip()).focus) { z = z.remove(); ++count; }
    z = z.zip().update([count,focus])
    return look_and_say_zipper(z)
}
const look_and_say = l => look_and_say_zipper(l.toZipper())
```

and execute...
```Javascript
// 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211

look_and_say(retake.of(2,1)) // 1,2,1,1
look_and_say(retake.of(1,2,1,1)) // 1,1,1,2,2,1
```

Both versions (a, b) of look_and_say function reduce the list recursively, while tracking and recording occurence of each element. 

In a) occurrence of an element and its value is appended to an accumulator, which becomes the result as the list is completely reduced. 
Using the *splitWhen* transform, we get occurrence and list of remaining elements.

In b) first occurrence of element is replaced by an array of [count, value], whereas consequent occurrences are removed. 
In the end, the *flatten* transform, pulls count and sticks it as an element that precedes the actual value. 
Note how the list is probed with *unzip/zip* Zipper transforms.
<commit_msg>added transducer code example<commit_after>Retake
=========================

Pragmatic data structure and algorithmic transformations for modern JavaScript apps.


## Installation
```
npm install --save retake
```

## Usage

- Node (6 or later)

```
let retake = require('retake')
```

- Browser (gzips to ~5k)

```Javascript
// es6
<script src="./node_modules/retake/lib/retake.js"></script>

// transpiled
<script src="./node_modules/retake/lib/retake.es5.js"></script>

// minified
<script src="./node_modules/retake/lib/retake.es5.min.js"></script>

// retake...

```

- For es5 versions - use [Babel polyfill](https://babeljs.io/docs/usage/polyfill/)

```Javascript
<script src="https://cdnjs.cloudflare.com/ajax/libs/babel-polyfill/6.13.0/polyfill.min.js">
</script>
```

## Introduction

ECMAScript, the language, lacks built-in support for advanced data structures. 
Arrays and Objects in JavaScript are highly efficient and provide a flexible API. 
However their mutative surface area does not serve well in design of concurrent systems. 
This is especially true for web apps (React, Flux, Redux et al.) where UIs can be described as a function of application state in a constant fold of events. 
Use of functional data structures is key to achieve referential transparency in such scenarios.

ES2015 has introduced game-changing features (for e.g. generator functions, lambdas, iteration protocols, proper tail calls) that improve performance and offer great flexibility in representing computations. 
As a result, we've benefited from libraries such as Immutable.js and Mori that offer an assortment of fully persistent data structures.

Retake takes a more pragmatic, refined approach in managing *pieces of data* your app cares about *at any given time*.
It is comprised of List, Zipper, and Transforms that enable proper organization of data for efficient traversal and updates. 
These functional concepts are implemented and exposed in a way to meet requirements of modern JavaScript apps. 
The end goal is to free app domain of procedural code by isolating the overhead of persistence and retrieval.

This implementation covers 3 important facets:

  - Lazy List - provides an immutable persistent collection to organize data linearly using head/tail decomposition with lazy evaluation.
  - Transforms - provide an integrated way to compose and apply algorithmic transformations to data structures.
  - List Zipper - facilitates efficient traversal and updates to encompassing linear data structure.

That's very much the gist of it! Try code examples below.

By the way, it should be clear that list-based structures are primarily purposed for sequential access unlike Vectors that are index-based.

Helpful readings:
- [Persistent Data Structure](https://en.wikipedia.org/wiki/Persistent_data_structure)
- [Transducers](http://clojure.org/reference/transducers) by <NAME>
- [Zipper](https://en.wikipedia.org/wiki/Zipper_(data_structure)) by <NAME>


## Code Examples

### 1. Transducers

```Javascript
let list = retake.of('react','om','angular','backbone','ember','knockout','meteor','vue','derby')
```
Let's transform this list.

a) Compose transforms directly
```Javascript
let t = filter(v => v.indexOf('r') > -1)(sort()(skip(1)(append)))
```

b) Use helper to compose transforms
```Javascript
let t = pipeT(filter(v => v.indexOf('r') > -1), sort(), skip(1))
// or
let t = composeT(skip(1), sort(), filter(v => v.indexOf('r') > -1))
```

Finally reduce over the list passing in the transducing function.
```Javascript
let result = reduce(t)(list)
console.log(...result) // derby ember meteor react

```

Chaining on objects...
```Javascript
//might be tempting
let result = list.filter(hasR).sort().skip(1)
console.log(...result) // derby ember meteor react

// _not_ recommended, read more on transducers to understand why
```


### 2. Look-and-say numbers

Watch this [video](https://youtu.be/ea7lJkEhytA?list=PLt5AfwLFPxWIL8XA1npoNAHseS-j1y-7V) by <NAME> for an introduction to this sequence.

Let's first implement a function that produces the "look and say" (next element in sequence).

a) Using Transforms on List
```Javascript
function look_and_say(l, acc=empty) {
    if(l.done) return acc
    let focus = l.first, count = 0
    let split = l.splitWhen(v => !(focus === v && ++count))
    acc = acc.append(count, focus)
    return look_and_say(split.tail.first, acc)
}
```

b) Using Zipper Transforms on List
```Javascript
function look_and_say_zipper(z) {
    z = z.unzip()
    if(z.focus === void(0)) return z.list.flatten()
    let focus = z.focus, count = 1
    while(focus === (z = z.unzip()).focus) { z = z.remove(); ++count; }
    z = z.zip().update([count,focus])
    return look_and_say_zipper(z)
}
const look_and_say = l => look_and_say_zipper(l.toZipper())
```

and execute...
```Javascript
// 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211

look_and_say(retake.of(2,1)) // 1,2,1,1
look_and_say(retake.of(1,2,1,1)) // 1,1,1,2,2,1
```

Both versions (a, b) of look_and_say function reduce the list recursively, while tracking and recording occurence of each element. 

In a) occurrence of an element and its value is appended to an accumulator, which becomes the result as the list is completely reduced. 
Using the *splitWhen* transform, we get occurrence and list of remaining elements.

In b) first occurrence of element is replaced by an array of [count, value], whereas consequent occurrences are removed. 
In the end, the *flatten* transform, pulls count and sticks it as an element that precedes the actual value. 
Note how the list is probed with *unzip/zip* Zipper transforms.

{'fraction_non_alphanumeric': 0.11018090839107006, 'fraction_numerical': 0.01607005388760585, 'mean_word_length': 4.472880463401791, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 35, 'https://': 10, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1127930', 'n_tokens_mistral': 3274, 'n_tokens_neox': 3008, 'n_words': 1197}