Flow annotations for recursive function

flow function type
flow interface function
flow template function
flow types
flow class constructor
flow implements
flow underscore
flow generics

I am interested in how to write flow type annotations for such function:

const Box = x => ({
  map: f => Box(f(x)),
  fold: f => f(x),
});

Type annotations should use Generics, I guess. Function usage example:

const getRandomColor = (): string =>
  Box(Math.random())
    .map(x => x * 0xFFFFFF)
    .map(Math.floor)
    .map(x => x.toString(16))
    .fold(x => `#${x.padStart(0, 6)}`);

P.S.: If it is impossible, please write a explanation Why it is impossible. Answer of @Isitea unfortunately doesn't fit because he changed the source code and that was not the point.


@Jared's answer only gets us part of the way, but beware of the things it's not enforcing.

How we'd like to write it using flow's generics

const Box = <A>(x:A): Box<A> => {
  return {
    map: <B>(f: A => B): Box<B> => Box(f(x)),
    fold: <B>(f: A => B): B => f(x),
  }
}

Given a simple function and a value of our box, we should be able to verify that the generic type constraint is enforced

const numberToString = (x: number) : string =>
  String (x)

const b : Box<string> =
  new Box("1")

b.map(numberToString) // wups! flow doesn't mind!

As of now, this is broken and doesn't work in flow. @mrkev shows us a workaround using a class

class Box<A> {
  x: A
  constructor (x: A) { this.x = x }
  map<B>(f: A => B): Box<B> { return new Box(f(this.x)) }
  fold<B>(f: A => B): B { return f(this.x) }
}

const numberToString = (x: number) : string =>
  String (x)

const stringToNumber = (x: string): number =>
  Number (x)

const b : Box<string> =
  new Box("1")

// flow accepts this valid program
b.map(stringToNumber)

// flow rejects this invalid program
b.map(numberToString)
//    ^ Cannot call `b.map` with `numberToString` bound to `f` because number [1] is incompatible with string [2] in the first argument.

@thehogfather shares another alternative with a pre-defined type. This is closer to the original form but requires an exhausting amount of typing - 2x what should be necessary if flow offered a more competent type system. Anyway it works, so we're not allowed to complain.

type Box<A> = {
  map: <B>(f: A => B) => Box<B>,
  fold: <B>(f: A => B)=> B
}

const box = <A>(x:A): Box<A> => {
  return {
    map: <B>(f: A => B): Box<B> => box(f(x)),
    fold: <B>(f: A => B): B => f(x),
  }
}

const numberToString = (x: number) : string =>
  String (x)

const stringToNumber = (x: string): number =>
  Number (x)

const b : Box<string> =
  box("1")

// flow accepts this valid program
b.map(stringToNumber)

// flow rejects this invalid program
b.map(numberToString)
//    ^ Cannot call `b.map` with `numberToString` bound to `f` because number [1] is incompatible with string [2] in the first argument.

GADTs and recursive types · Issue #1356 · facebook/flow · GitHub, With this pattern, values of type Tree<A> are functions that are applied to access Certain recursive types cannot currently be checked with Flow. with no type annotation, in case consumers have configured Flow to use a  1 Answer 1. In a flow chart, you don't normally add multiple invocations for things like loops, you would just indicate that the code may be repetitively called until a condition is met. So, for a recursive function, it would be similar - the base case is a regular step and the recursive step is the same as loop.


UPDATE:

Not sure if it's possible, there's a link in the comments to a counter-example for the map method.

Original Answer:

Yes! It is indeed possible:

const Box = <T1>(x:T1): Box<T1> => {
  return {
    map: <T2>(f): Box<T2> => Box(f(x)),
    fold: <T3>(f): T3 => f(x),
  };
};

function takesBoxedString (b: Box<string>):string { return b.fold(s => s + '') }
let boxedNum = Box(3);
let boxedString = Box('foo');

takesBoxedString(boxedString); // fine
takesBoxedString(boxedNum);    // compiler complains

I didn't know much about flow generics when I started this, but boy howdy do I have a much better appreciation for them now. Here's the playground.

Generic type constraint ignored in higher-order function · Issue , The annotation of the site type is requested to be {s0}Up in the typing derivation. The flow annotation shows the recursive nature of the function f. After calling the  Adding type annotations is an important part of your interaction with Flow. Flow has a powerful ability to infer the types of your programs. The majority of your code can rely on it. Still, there are places where you’ll want to add types. Imagine the following concat function for concatenating two strings together.


I'm not sure what you want.

If you are using 'flow type checker with babel', I think following code is what you want to get.(Tested with flow.org )

/* @flow */

const Box = ( x: string | number ): Box => ( {
    toNumber: ( f: Function ): Box => Box( f( x ) ),
    toString: ( f: Function ): string => f( x )
} );
const getRandomColor = (): string =>
    Box( Math.random() )
    .toNumber( ( x: number ): number => x * ( 2 ** 32 ) )
    .toNumber( Math.floor )
    .toString( ( x: number ): string => x.toString( 16 ) )
    .toString( ( x: string ): string => `#${x.padStart( 6, "0" )}` );

Mobile Computation with Functions, Just like in functions, class methods can have annotations for both parameters (​input) and returns (output). 1 2 3, class MyClass { method(  Recursive functions use something called “the call stack.” When a program calls a function, that function goes on top of the call stack. This similar to a stack of books. You add things one at a time. Then, when you are ready to take something off, you always take off the top item.


Class Types, Here is a sample flow function for call and return instructions: fvx : gpyqwpσq rx ÞÑ An approach that avoids the burden of annotations, and can capture what a​. Flowcharts and Recursion. Since both the usual form of computer program and recursive function definitions are universal computationally, it is interesting to display the relation between them. The translation of recursive symbolic functions into computer programs was the subject of the rest of this report.


[PDF] Lecture Notes: Interprocedural Analysis, The process in which a function calls itself is known as recursion and the corresponding function is called the recursive function. The popular example to. To understand the control flow for a recursive you need to understand the basics of a stack data structure. Also, you should know that while execution of a program memory can be allocated to various instances of the same function.


C++ Recursion with example, So, the recursion reduces a function call to a simpler one, and then – to the execution of a function: where the control flow is now, the current  To build complex, but maintainable Flows, it is important to be familiar with this next step. The Flow blog calls this Nested Flows , so I will stick with this term.&nbsp; What this really is in essence, is how to build Flows as a reusable function or service.&nbsp; I want to then