Forem: Hemaka.com

Lazy Recursion Using JavaScript Generators

Babak — Mon, 22 Jul 2019 07:43:31 +0000

Introduction

Generators and Iterators enable lazy evaluation in JavaScript. Used in a loop, for example, executions "pauses" at each yield statement until the next iteration is requested. What is often overlooked is that generators can be recursive functions. In this brief article, I'll go over a simple example that demonstrates how one can create a recursive generator function for lazy evaluation.

Yield

Most documentation on generators provide iterative examples, often using a while or for construct with a yield statement. For example, a simple generator that yields sequential numbers could be written like this:

function* count() {
  let count = 0
  while( true ) {
    yield count++
  }
}

Iteration is fine; but what about algorithms that are better expressed recursively? How can we use generators to create lazily evaluated recursive functions? We do this by delegating to another generator.

The yield* keyword (with asterisk)

Meet yield*, the lazier cousin of the yield statement. The yield statement pauses with the next value until requested. On the other hand, the yield* statement (with an asterisk) simply defers to another iterator object.

Evaluation doesn't actually stop at yield*, it is merely a syntax to indicate that we'll forward all yields from the given iterator object until it finishes--after which we resume. It turns out, this is quite powerful.

For our first example, let's suppose we want to loop over an iterable, endlessly. We could do this as follows:

function* loop( iterable ) {
  yield* iterable
  yield* loop( iterable )
}

For our second example, we'll look at a more concrete scenario--here is a function that generates array permutations using Heap's Permutation algorithm:

function* heapsPermutationsMutating( source, end = source.length  ) {
  // base case
  if( end === 1 ) { yield [ ... source ] }

  // branch
  for ( var index = 0; index < end; index++ ) {
    yield* heapsPermutationsMutating( source, end - 1 );
    swap( source, end - 1, end % 2 === 0 ? index : 0 )
  }
}

function* heapsPermutations( source ) {
  yield*  heapsPermutationsMutating( source )
}

function swap( arr, i1, i2 ) {
  return [ arr[ i1 ], arr[ i2 ] ] = [ arr[ i2 ], arr[ i1 ] ] 
}

Notice that we don't need to build and keep the resulting array because we yield each permutation and move on. The yield* keyword defers to the yield given in the base case reached at the end of each recursive branch.

This pattern works great for many recursive solutions. What makes the approach great in terms of space and time complexity is that we can stop execution after we get our desired result--we don't need to generate all permutations.

To illustrate this, here is a take generator function that we can use to only create a specific number of permutations.

function* take( num, iter ) {
  let item = iter.next()
  for( let index = 0; index < num && !item.done ; index++) {
    yield item.value
    item = iter.next()
  }
}

To take just the first 5 permutations of an array, we might do something like this:

let permutate5 = [ ...take( 5, heapsPermutations([1,2,3,4,5]) ) ]

Conclusion

Recursive lazy evaluation further improves JavaScript's functional capabilities. It shouldn't be overlooked! Many algorithms are expressed much more elegantly and naturally when written recursively. Recursive functions are just as capable of lazy evaluation as their iterative counterparts.

Dynamically Check Function Parameters Before Runtime

Babak — Mon, 29 Apr 2019 06:57:24 +0000

Prelude

Thanks to TypeScript's conditionals and self-referencing types; it is possible to instruct the compiler to make dynamic choices. This is what I mean by "dynamic"--of course, TypeScript is still a static compile-time type checker.

Introduction

In TypeScript, it is possible to restrict the value that can be assigned to a generic using extends however, there are limitations. In this article we will see how the we can use Type Aliases and the intersection operator & to enhance the kinds of limitations we can place on generics

On Generics

In TypeScript, generics enable us to express polymorphic functions, objects that deal with a variety of types, the return value of a function, and more. One could think of a generic as essentially a variable or a placeholder that is assigned to, so long as its not being widened in the process. By default, generics accept type {}, which is pretty much anything in JavaScript. For example:

declare function id<A>( a: A ) : A

Anything we provide variable a is going to be the type of generic A. But we can also restrict a generic before an assignment. Consider this map function:

declare function map<A, B, FN extends (a:A) => B>( xs: A[], fn: FN ) : B[]

The compiler will expect FN to be a function that takes an A to B. A and B can be anything; but FN has to be a function with an arity of one. This is because FN is already narrowed down to be a function of the given structure through the use of extends.

But there are limits to what we can do. What if, for example, we want to construct a merge function that statically checks that neither of two objects share any keys?

We might start by creating a Type Alias that returns shared keys between two objects:

type CommonKeys< A, B > = Extract<keyof A, keyof B>

But we can't do this:

type Validate<A,B> = CommonKeys<A,B> extends never ? B : never
// 🚫 Error, B has a circular constraint
declare function safeMerge< A, B extends Validate<A,B>>( 
  objA: A, 
  objB: B 
): A & B

B cannot reference itself when declared; and conditionals are not allowed in declarations anyway. So how do we go about this?

Intersections

To solve this problem, we observe that the intersection of any type with itself is itself; and with never it is always never. As such, we first assign the generic and then validate using an intersection. Let see how we can use this to construct a merge function that requires both objects to have unique keys:

type CommonKeys< A, B > = Extract< keyof A, keyof B > 
declare function safeMerge< A, B >( 
  objA: A, 
  objB: B & ( 
    CommonKeys<A,B> extends never 
      ? B // B & B is B
      : never // B & never is never
  ) 
): A & B

Does it work?

// 🚫 Error
const mergedObj = safeMerge( { a: 1 }, { a : 2, b: 3 } )

Good, we get a compiler error! Both objects overlap on key 'a', which we don't want to allow.

// ✅ Works!
const mergedObj = safeMerge( { a: 1 }, { b : 2 } )

It works! Neither object shares a key and our merge will not overwrite any key-value pairs.

The Validation Type Alias as a Pattern

This bit of type code requires us to think about what is happening here:

 B & ( 
    CommonKeys<A,B> extends never 
      ? B // B & B is B
      : never // B & never is never
  )

We can make this a bit more concise using three helpers:

type IsNever<T> = [T] extends [never] ? 1 : 0;
type WhenNever<Evaluate,Return> = IsNever<Evaluate> extends 1 ? Return : never
type WhenNotNever<Evaluate,Return> = IsNever<Evaluate> extends 1 ? never : Return

If you're curious as to why IsNever puts T inside of an array, it is to prevent union distribution. We want to see if T is never and not if its union may contain never. We'll use this test to determine if want to raise a compiler error or not.

For merge function, we'll want to create an error when A and B share keys. We don't want to allow keys to be overwritten. No common keys will result in never, which is what we want. So we'll construct our type helper as follows:

/**
 * Validates that keys in object A do not overlap with object B
 * return A if true and never if not.
 */
type ValidateKeysDontOverlap<A,B> = WhenNever< CommonKeys<A,B>, A >

We can tuck this away into a type validation library and follow a convention where all validating types start with Validate. Then we can use it like this:

declare function safeMerge< A, B >( 
  objA: A, 
  objB: B & ValidateKeysDontOverlap<B,A>
): A & B

A Validation Type Standard

It could be useful if this pattern were standardized around some convention. My personal thought at the moment is that a validation type should return the first parameter if valid and never if not. In this order because TypeScript type aliases can have optional generics, for example:

type Example<A,B = A> = ....

Here the second generic B will be set to A, if not passed. So at least the first parameter will be required. However, as far as I know, not a lot of people are talking about this yet and the range of use cases known to me are limited to my own.

Conclusion

TypeScript enables us to narrow down the range of what a generic can be within some limitations. We can overcome those limitations by intersecting a generic with a Type Alias which will statically compute complex situations and return the same type we are intersecting with or never if we want to cause the compiler to complain about the result of our static analysis.

To better communicate what we are doing, it might be useful to adopt some standard for this pattern. A type alias intended for this kind of pattern might start with the name Validate and return either the first parameter it requires or a type never otherwise.

Introducing The Recursive `Pipe` and `Compose` Types

Babak — Fri, 12 Apr 2019 01:05:26 +0000

It turns out, the recursive Pipe (and Compose) types offer key advantages over the traditional method of using parameter overloading. The key advantages are:

Preserve variable names
Better tolerance of generics in function signature
Variadic entry function
Can theoretically compose unlimited functions

In this article, we'll explore how such a Pipe and Compose type are built.

If you want to follow along with the full source at hand, see this repo:

https://github.com/babakness/pipe-and-compose-types

Introduction

My journey for this project starts as a challenge to create recursive Pipe and Compose types, without relying on overloads that rename the parameters. To review an example of how to build this with overloads follow one of these links to the excellent library fp-ts by @gcanti

Pipe:

https://github.com/gcanti/fp-ts/blob/master/src/function.ts#L222

Compose:

https://github.com/gcanti/fp-ts/blob/master/src/function.ts#L160

I've used this strategy in my own projects. Parameter names are lost and are replaced, in this case, with alphabetic names like a and b.

TypeScript shares its ecosystem with JavaScript. Because JavaScript lacks types, parameter names can be especially helpful in guiding usage.

Let's look at how these types work a bit closer.

Make a Recursive Pipe Type

First, we're going to need some helper types. These are going to extract information from a generic function:



export type ExtractFunctionArguments<Fn> = Fn extends  ( ...args: infer P ) => any  ? P : never
export type ExtractFunctionReturnValue<Fn> = Fn extends  ( ...args: any[] ) => infer P  ? P : never

Next two more helpers, a simple type to allow us to branch different types predicated on the test type and a short hand for express any function.



type BooleanSwitch<Test, T = true, F = false> = Test extends true ? T : F
export type AnyFunction = ( ...args: any[] ) => any

This next type is really esoteric and ad-hoc:




type Arbitrary = 'It was 1554792354 seconds since Jan 01, 1970 when I wrote this' 
type IsAny<O, T = true, F = false> = Arbitrary extends O
  ? any extends O
    ? T
    : F
  : F

Essentially, this type detects any and unknown. It gets confused on {}. At any rate, it isn't exported and intended for internal use.

With those helpers in place, here is the type Pipe:



type Pipe<Fns extends any[], IsPipe = true, PreviousFunction = void, InitalParams extends any[] = any[], ReturnType = any> = {
  'next': ( ( ..._: Fns ) => any ) extends ( ( _: infer First, ..._1: infer Next ) => any )
    ? PreviousFunction extends void
        ? Pipe<Next, IsPipe, First, ExtractFunctionArguments<First>, ExtractFunctionReturnValue<First> >
        : ReturnType extends ExtractFunctionArguments<First>[0]
          ? Pipe<Next, IsPipe, First, InitalParams, ExtractFunctionReturnValue<First> >
          : IsAny<ReturnType> extends true
            ? Pipe<Next, IsPipe, First, InitalParams, ExtractFunctionReturnValue<First> >
            : {
              ERROR: ['Return type ', ReturnType , 'does comply with the input of', ExtractFunctionArguments<First>[0]],
              POSITION: ['Position of problem for input arguments is at', Fns['length'], 'from the', BooleanSwitch<IsPipe, 'end', 'beginning'> , 'and the output of function to the ', BooleanSwitch<IsPipe, 'left', 'right'>],
            }
    : never
  'done': ( ...args: InitalParams ) => ReturnType,
}[
  Fns extends []
    ? 'done'
    : 'next'
]

This type goes through a series of steps, it starts by iterating through each function, starting at the head and recursively passing the tail end to the next iteration. The key to making this work is to extract and separate first item in the array of functions from the rest using this technique:



( ( ..._: Fns ) => any ) extends ( ( _: infer First, ..._1: infer Next ) => any )

If we didn't do error checks, we could distill this next part as simply



PreviousFunction extends void
        ? Pipe<Next, IsPipe, First, ExtractFunctionArguments<First>, ExtractFunctionReturnValue<First> >
        : Pipe<Next, IsPipe, First, InitalParams, ExtractFunctionReturnValue<First> >

PreviousFunction is void only on the first iteration. In that case we extract the initial parameters. We pass InitialParams back in each iteration with the last functions return type. Once we exhaust all functions in the list, this part



 Fns extends []
    ? 'done'
    : 'next'

returns done and we can return a new function made up of the initial parameters and the last return type



'done': ( ...args: InitalParams ) => ReturnType,

The other bits are error detection. If it detects an error, it will return custom object which will point to the count were the error occurred. In other words, it has built-in error reporting.

I learned about this technique studying other people's libraries. One notable example is typescript-tuple which we use later to construct Compose

Alright now let's create an alias for the pipe function itself



type PipeFn = <Fns extends [AnyFunction, ...AnyFunction[]] >( 
  ...fns: Fns & 
    Pipe<Fns> extends AnyFunction 
      ? Fns 
      : never 
) =>  Pipe<Fns>

Here is another technique to illustrate. When our Pipe function return that helpful error object, we want to actually raise a compiler error too. We do this by joining the matched type for fns conditionally to either itself or never. The later condition creating the error.

Finally, we're ready to define pipe.

I do this in a different project, not only in a different file in the same project. I do this for two reasons:

First, I want to separate the implementation from the type. You're free to use these types without potentially including any JavaScript.

Second, once the type has compiled correctly, I want to separate the pros and cons of future TypeScript versions from the type and implementation.

Implementing The Pipe Function



export const pipe: PipeFn =  ( entry: AnyFunction, ...funcs: Function1[] ) =>  ( 
  ( ...arg: unknown[] ) => funcs.reduce( 
    ( acc, item ) => item.call( item, acc ), entry( ...arg ) 
  ) 
)

Let see it work:



const average = pipe(
  ( xs: number[]) => ( [sum(xs), xs.length] ),
  ( [ total, length ] ) => total / length
)

✅ We see average has the right type (xs: number[]) => string and parameter names are preserved.

Let's try another example:



const intersparse = pipe( 
  ( text: string, value: string ): [string[], string] => ([ text.split(''), value ]),
  ( [chars, value]: [ string[], string ] ) => chars.join( value )
)

✅ Both parameter names are preserved (text: string, value: string) => string

Let's try a variadic example:



const longerWord = ( word1: string, word2: string ) => (
  word1.length > word2.length 
    ? word1 
    : word2
)
const longestWord = ( word: string, ...words: string[]) => (
  [word,...words].reduce( longerWord, '' )
)

const length = ( xs: string | unknown[] ) => xs.length

const longestWordLength = pipe(
  longestWord,
  length,
)

✅ Parameter names and types check, the type for longestNameLength is (word: string, ...words: string[]) => number

Great!

Compose

It turns out we can do this for Compose very easily. The helper we need we'll use from typescript-tuple.



import { Reverse } from 'typescript-tuple'
export type Compose<Fns extends any[]> = Pipe<Reverse<Fns>, false>
export type ComposeFn = <Fns extends [AnyFunction, ...AnyFunction[]] >( 
  ...fns: Fns & 
    Compose<Fns> extends AnyFunction 
      ? Fns 
      : never 
) =>  Compose<Fns>

The implementation is only slightly different



import { ComposeFn } from 'pipe-and-compose-types'
export const compose: ComposeFn = ( first: Function1, ...funcs:  AnyFunction[] ): any => {
  /* `any` is used as return type because on compile error we present an object, 
      which will not match this */
  return ( ...arg: unknown[] ) => init( [first, ...funcs] ).reduceRight( 
    (acc, item) => item.call( item, acc ), last(funcs)( ...arg ) 
  )
}

Let's put our new compose to the test:



const longestWordComposeEdition = compose(
  length,
  longestWord,
)

✅ Parameter names and types check, the type for longestNameLength is (word: string, ...words: string[]) => number

Closing

I encourage you to take a look at this repo to review the types

https://github.com/babakness/pipe-and-compose-types

to import the types into your own project, install using:

npm install pipe-and-compose-types

Also look at two great application of these types

https://github.com/babakness/pipe-and-compose

import these functions into your project using

npm install pipe-and-compose

Please share your thought! Feel free to reach out to me on Twitter as well!