DEV Community: Tyler Roberts

JS Symbol Iterators & Generators - An Exercise

Tyler Roberts — Mon, 01 Feb 2021 11:03:43 +0000

What is function, yield and yield?

Brief
A Linked List
- Iterator Logic
- yield*
- Reverse the data
- Did the child become a parent?
Let's Apply it and Test
Repl
- Recap
- Destructuring parameters from next via yield

Brief

When you iterate over lists it's probably intuitive now for most to use Array.map(). However, many of us also like to generate our lists based on some range, not by way of data but some application logic defined number. Usually, I'll import lodash.range or create a range helper. What about specific sequences like Fibonacci? Well here we can take the power of large, possibily infinite size lists. Normally large lists would hurt performance if it's particularly large even in O(n).

Essentially we're creating a lazy loaded sequence.

In a lot of libraries today we have lazy load as a common way of handling lists of data that may be large in length or in size per element; image galleries.

Without writing a lot of helpers, importing libraries, or getting caught in cumbersome type associations as boilerplate, we can look at built-in Generators.

Now when we define our applications sequences or even the json we may use, we can immediately "close the faucet" of the flow of that data. Only opening it when we need it, making it reusable, and allowing us to completely throw it out if we need to start over.

A Linked List

Given a list of data we can look at a list of lists to get started:

const familyTree = [
    ["Adam", "Jane", "Doe"],
    ["Jane", "Peter", "Mary"],
    ["Mary", "Liam", "Olivia"],
    ["William", "Ava", "Lucas"]
]

Here we have a "sorted" list going from familyTree[0] being the earliest generation and last index being the oldest.

Let's assume that the first of each is the "Child" and the other two are biological "Parents".

Iterator Logic

Let's start by creating our familyTree iterator logic.

function* genList(p1, p2) {
    const genealogy = [...familyTree].reverse();
}

I choose to work backwards from generation, given our data, and spread operator to prevent mutation.

In this data our familyTree contains the newest generation at the head or first of the list. So we can reverse the list before we start.

yield*

We could easily create a map of each element very quickly with yield* to simply "iterate" the given data, and give us each Array within familyTree, but where's the fun in that. Our generator should have some logic, and yield genealogy[i] conditionally!

To clarify what * does, we can look at yield*:

function* genList() {
   yield* [...familyTree].reverse();
}

let i = genList();
console.log(i.next().value); //  [ 'William', 'Ava', 'Lucas' ] 
console.log(i.next().value); //  [ 'Mary', 'Liam', 'Olivia' ]

Now let's search to find who we're actually looking for with p2 or person2

Let's imagine it's "Olivia"
- ["William", "Ava", "Lucas"] is first since we reversed, so we can skip over it

Reverse the data

function* genList(p1, p2) {
    const genealogy = [...familyTree].reverse();
    let start = 0, end = genealogy.length - 1;
    for (const i in genealogy) {
        if (genealogy[i].includes(p2)) {
            start = +i // coerce typeof i to number from string
        }
        if (genealogy[i].includes(p1)) {
            // Exercise: what would go here, and why?
            // leave a comment below 😉
        }
    }

Now that we can rule out names that aren't even in here.

Let's loop through our reduced list by finding links in each family array, for preceding arrays;

or "blood" relation
see: Linked List

Did the child become a parent?

main.js

function* genList(p1, p2) {
    [...]


    // |-> Read along
    // Iterator Logic
    for (let i = start; i <= end; i++) {
        // yield will send over the first family
        let link = yield genealogy[i]
        // with .next(Child) we can pass over a name 
        // from the above: yield genealogy[i]
        // to the above: link
        if (link && (i + 1) <= end) {
            let [_, ...parents] = genealogy[i + 1]
            // Did that child became a parent?                      
            // Let's see if parents include the link
            if (parents.includes(link)) {
                yield genealogy[i]
            }
        } else {
            // but if there's no subsequent links...
            break;
        }
    }
}

Let's Apply it and Test

main.js

/**
 * 
 * @param p1 Child
 * @param p2 Relative
 */
const isGenerational = (p1, p2) => {
    let link;

    // generate genealogy with lower and upper bounds
    const ancestry = genList(p1, p2)
    // get Child from each family and yield links 
    for (const [ancestor] of ancestry) {
        (ancestor === p1)
            // if p1 is found, we can throw the list away
            ? link = ancestry.return(true)
            // if linked list continues
            : link = ancestry.next(ancestor)

    }
    return (link.done && link.value)
}

(async () => {
    console.log(
        (isGenerational("Adam", "Olivia") === true),
        (isGenerational("Adam", "Lucas") === false),
        (isGenerational("Jane", "Liam") === true),
        (isGenerational("Mary", "Ava") === false),
    )
})();

Repl

Recap

Destructuring parameters from next via yield

Let's look at this very peculiar statement.

let link = yield genealogy[i]

It's the initialization that makes it useful.

We can send data over initially, and wait for any data that may be contextual.

let whatAboutThis = yield context[i]
if (whatAboutThis) {
    // perform check, updates, hydrate, whatever
    await updateContext(whatAboutThis)
    yield context["imaginary"]
}

Essentially when our function obtains something we can have our iterator pass it up to the generator and allocate a new yielded value.

const iterator = contextSequence(); // generates sequence of "context"
let water = iterator.next("hydrate"); // <- gets passed to `whatAboutThis` 
water.value // -> value stored of context["imaginary"]

I can imagine reactive state handlers here. Imagine a federal reserve of some data that is only accessed when stores are low; lazy loaded galleries.

Great way to handle large queues that run async but not AOT.

I'm thinking debounce function for subscribed events that aren't time critical. Although I'll need to play around with it a bit. Almost every example showcases take on infinite lists, so it's very functional.

Introduction to Functional Programming with Typescript

Tyler Roberts — Fri, 15 Jan 2021 21:14:43 +0000

This is the beginning of a series of short guides on functional programming, much of what I've posted on reddit, I'm compiling for dev.to.

I finally went back to try and learn functional programming, and realized that the type structure of the function composition is in itself data! My old friend Zac tried to teach me this many years ago, et voila. This helped me better understand currying and higher order functions. For example:

const K  = a => b => a;   
const KI = a => b => b;

K is technically a Kestrel combinator or first function or constant function. KI is a Kite combinator or second function. You can copy and paste these into the console (F12) and test it out.

K(1)(0)  // ->  1
KI(1)(0) // ->  0

I think Typescript actually helps us here to make sense of what we're going to do next so let's create a type association.

const T = K 
const F = KI

// pretend we're in a .ts file  
type BOOL = T | F;

So BOOL simply says it's either T or F (true or false) like any basic Boolean.

Keep in mind that T and F are still just functions K and KI

So we can create an AND function that takes T and T and returns True; or F and T and returns False. This AND function will look a bit weird but bare with me.

const AND = p => q => p(q)(p);

We pass in a function to parameter p and curry another argument (function) to parameter q so that p(q)(p) will return us a function of p. These are higher order functions or curried functions that we define and expect to pass around in our program. This is just a discipline to writing programs and comes from lambda calculus. Immediately this will probably seem very odd, and I'll try to break it down.

AND(T) gives us q => p(q)(p), or essentially q => T(q)(T). Well we know T returns whatever it's first argument is(a => b => a). So if q is F it will be F.

We can satisfy parameter q with argument F. AND(T)(F) or T(F)(T). We're not calling F but passing it in. Now this means we satisfy every functional parameter for T.

Essentially AND(T)(F) becomes T(F)(T) but what's different is AND sets up the second parameter as first argument in T. You can run T(T)(F) in the console and get a => b => a. T(F)(T) is a => b => b .. imagine AND(T)(F) as T => F => T(F)(T).

If this doesn't immediately make sense that's ok (I'm trying my best 😅). We can simply run it in the browser instead!

AND(T)(T)  // -> a => b => a 
AND(T)(F)  // -> a => b => b 
AND(F)(T)  // -> a => b => b 
AND(F)(F)  // -> a => b => b

The resulting value from AND(T)(T) is the function composition we passed in, T! So the type association of a => b => a as we've already defined in our program (or console in this case) is typeof T in type BOOL.

// main.ts
// Compiles! ✅
const K = a => b => a;
const KI = a => b => b;

type TRUE = typeof K;
type FALSE = typeof KI;

type BOOL = TRUE | FALSE;

const AND: BOOL = p => q => p(q)(p);

(async (): Promise<FALSE> => {
    const falsey: BOOL = AND(K)(KI);
    return falsey;
})();

Now you're more likely to see pure FO in other languages like lisp, clojure or haskell so if this scares you, don't worry! There's a reason C# is OO and F# is FO, trying to write FO in something like typescript is cumbersome without default lazy loaded lists etc.
I think running it in the browser first hand (in js) is a great way to learn how the composition of functions itself can be treated as data.

I find this fascinating. There's definitely a better explanation out there but this is how I came to understand it after finally revisiting it. That euphoric feeling of when something clicks after many months of attempts to understand something is the best and never gets old!

Next: How to compose a NOT function -- ⏭⌛