Here is an interesting JavaScript implementation of the Y-combinator:
const Y = g => (x => g(x(x)))(x => g(x(x)))
//or
const Y = f => {
const g = x => f(x(x))
return g(g)
}
I've been thinking, could it be possible to create a TypeScript generic version of the Y-combinator?
type Y<F> = ???
The concise answer:
To define a fixed point combinator in TypeScript for a one-argument function, you can use the type:
type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;For a more detailed explanation, read on:
When creating a fixed point combinator, it should be designed as a generic function structured like this:
type Fixed = <T>(f: (t: T) => T) => T;
This type allows you to call it with any single-argument function that returns the same type as its input and obtain the fixed point of that function after repeated application.
An example is provided where iteration on a well-behaved function `f` approximates the fixed point computation:
const fixed: Fixed = f => {
let r = null as any;
for (let i = 0; i < 1000; i++) r = f(r);
return r;
}
While this implementation may not follow the classic approach, it serves the usual purpose of finding fixed points for functions taking other functions as inputs.
Illustrated further is defining a `protoFactorial` function whose fixed point yields the recursive calculation of a non-negative integer's factorial:
const protoFactorial = (f: (n: number) => number) =>
(n: number) => n === 0 ? 1 : n * f(n - 1)
In this case, `f` signifies a function `(n: number) => number`, where the output provides another function of the same type, processing the input `n` representing the target factorial value. If `n` equals zero, the function returns `1`; otherwise, it yields `n * f(n - 1)`.
By using the fixed point combinator `fixed`, you can successfully generate the intended factorial function:
const factorial = fixed(protoFactorial);
console.log(factorial(7)); // 5040
All operations work seamlessly with this setup.
However, when dealing specifically with the Y combinator, the expectation often involves operating on types where `T` itself is a function type. Consequently, it seems appropriate to assign a unique generic type to `Y` connected to the `T` function type's input and output:
type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;
Essentially, this mirrors `Fixed` by substituting `T` with `(i: I) => O`. A probable usage scenario for an instance `Y` of type `Y` should involve calling `Y(protoFactorial)` to acquire the desired `factorial` result.
A TypeScript-based implementation of `Y` is outlined as follows:
interface Ω<T> {
(x: Ω<T>): T;
}
const Y: Y = <I, O>(F: (f: (i: I) => O) => (i: I) => O) =>
((x: Ω<(i: I) => O>) => F(x(x)))((x: Ω<(i: I) => O>) => F(x(x)));
To enforce strong typing in the Y combinator implementation, a recursive type `Ω<T>` becomes essential; the parameter `x` necessitates adherence to such a type requirement for enabling a functional `x(x)` invocation yielding an output matching `O (i: I) => O`.
The above version aligns closely with your original statement regarding implementation, though adopting `F` instead of `g` and incorporating type declarations for enhanced compiler clarity.
Despite addressing the initial inquiry satisfactorily, utilizing the `Y` combinator directly within JavaScript encounters drawbacks due to the language's eager evaluation strategy, leading to premature execution of all function arguments before engaging the function body:
try {
const factorial = Y(protoFactorial);
} catch (e) {
console.log(e); // too much recursion
}
Given an illustration where invoking `Y(protoFactorial)` expands infinitely to entail continuous `F(F(F(F(F(F(...))))))` calls, a run-time crash ensues.
To resolve such runtime issues and secure a robust fixed-point combinator tailor-made for JavaScript, opting for an alternative akin to the Z combinator proves effective as it integrates eta abstraction concepts to create `v => x(x)(v)` for deferred `x(x)` computations:
const Z: Y = <I, O>(F: (f: (i: I) => O) => (i: I) => O) =>
((x: Ω<(i: I) => O>) => F(v => x(x)(v)))((x: Ω<(i: I) => O>) => F(v => x(x)(v)));
Upon integrating `Z` in lieu of `Y`, successful execution outcomes are achieved:
const factorial = Z(protoFactorial);
// const factorial: (i: number) => number
console.log(factorial(7)); // 5040
If merely concerned with typings without feigning limitations around JavaScript and TypeScript capabilities pertaining to first-class recursion at runtime, a more straightforward recursively defined function of type `Y` can be fashioned:
const R: Y = f => f(x => R(f)(x))
console.log(R(protoFactorial)(7)) // 5040
From a type system outlook, `fixed`, `Y`, `Z`, and `R` all conform to values encapsulating the `Y` structure:
function acceptY(y: Y) { }
acceptY(fixed)
acceptY(Y)
acceptY(Z)
acceptY(R)
Hence, conclusively asserting that the TypeScript definition for a fixed point combinator operating on a single-argument function comprises:
type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;
Currently, I'm utilizing TypeScript in this particular file. import React, {Component} from 'react' import {Map, InfoWindow, Marker, GoogleApiWrapper, mapEventHandler, markerEventHandler} from 'google-maps-react'; import { coordina ...
Hello there! I'm fairly new to working with TypeScript and I've encountered an issue with a piece of state in a child component. I'm trying to modify it based on the previous value, but every time I call the setState function, I get a type e ...
I have been attempting to implement AWS X-Ray for all lambda functions in the following manner: serverless.yml provider: tracing: lambda: true apiGateway: true name: aws runtime: nodejs8.10 stage: ${opt:stage, 'dev'} region: ...
I have received data from an API in the form of an array with objects structured like so: [ {"desc":"a", "menu": 1},{"desc":"b", "menu": 2},{"desc":"c", "menu": 1}, ...
Just diving into Angular testing and decided to test out the checkLogin function within my application. import { Component, OnInit } from '@angular/core'; import { Router } from '@angular/router'; import {AuthenticationService} from &qu ...
Currently in my project, I utilize backbone.js along with typescript. My goal is to incorporate backbone-forms for form creation, however I am unable to locate a typescript definition file (d.ts) for this specific backbone plugin. Despite my attempts to cr ...
I am facing an issue with my array and component functions. Each component has a handleRemove function that is supposed to remove the selected component from the array. However, the function is not working as expected. Instead of deleting just the selected ...
In my code, there is a function that accepts only numeric variables. function add(n1: number) { return n1 + n1; } However, I mistakenly initialized a variable with type "any" and assigned it a string value of '5'. let number1; number1 = &apo ...
In my TypeScript project, I encountered a situation that could be simplified as follows: Let's take a look at the type Type: type Type = { a: number; } | { a: number; b: number; } | { a: number; b: number; c: number; }; I proceed to defi ...
INTRO I built an e-commerce app with TypeScript and Sequelize ORM. In the app, I have a table that generates sequential invoice numbers based on the current day. CREATE TABLE `dm_generate_trx` ( `id` int NOT NULL AUTO_INCREMENT, `date` date NOT NULL, ...
I'm having trouble with my TypeScript filter function. Here is an array of objects: [ { "id": 12345, "title": "Some title", "complexity": [ { "slug": "1", // This is my search term "name": "easy" }, { ...
During the time of RC4, I was able to create my own custom http instance using a function like this: export function createHTTP(url:string, headers?:Headers){ let injector = ReflectiveInjector.resolveAndCreate([ myHttp, {provide:'defaultUrl ...
Here is a snippet of my simple express code: const api = Router() api.post('/some-point', async (req, res, next) => { const someStuffToSend = await Promise.resolve("hello"); res.json({ someStuffToSend }); }) In my development environmen ...
When running this tsx code: import React from "react"; import BaseButton from "@mui/base/Button"; import styled from "@emotion/styled"; export const enum BUTTON_TYPE { MAIN = "main", LINK = "link", } ...
I have configured the redux store in a public library as follows: import { configureStore } from '@reduxjs/toolkit'; import rootReducer from '@/common/combineReducer'; import { createLogger } from 'redux-logger'; import thunk ...
I've encountered an issue where the code below removes all spaces, but it's also removing the enter key. Is there a way to remove only spaces and not affect the enter key? static stripDoubleSpaces(str: string): string { if (!!str) { ...
As I've developed a Directive that incorporates various Css classes, it would greatly enhance its flexibility if the Css classes could be configured at Application start within the config section. I believe utilizing a provider is the appropriate appr ...
I am in the process of creating a build script using only npm, without relying on grunt or gulp. Most aspects are functioning well except for concatenating typescript files. While I can compile individual typescript files successfully, I am faced with th ...
Working with node.js and various email addresses, I encountered a compile error: TS2345: Argument of type '(error: any, document: any) => void' is not assignable to parameter of type '(err: any) => void'. This error occurs at ...
I developed a react hook that resembles the following structure: export const useForm = <T>(values: T) => { const [formData, setFormData] = useState<FormFieldData<T>>({}); useEffect(() => { const fields = {}; for (const ...