Typed currying and partial application?

[jasonkuhrt]

Hi,

Thanks for open-sourcing flow.

I started thinking about how I could combine flow with currying and/or partial application such as my purry

Consider this example:

var add = purry(a: Number, b: Number => a + b)

map(add(4), List.of(1, 2, 3))
// => List [5, 6, 7]


map(add("FOOBAR"), List.of(1, 2, 3))
// => FLOW TYPE ERROR!

Here's where it gets ugly. A type system like Haskell would simply catch the issue here:

add("FOOBAR")

However in the case of flow it must wait until the add4 function is invoked with a member from numbers to discover that a non-number was passed as the first argument to add. This is because purry or ANY currying implementation in JavaScript will collect the arguments until completion before invoking the wrapped function (add in the case above). The implication is that the user _will not be shown where he made the mistake_ (add("FOOBAR")) but rather a type error coming from within the guts of the purry implementation. It will suck.

flow demonstrates practicality for a variety of common but somewhat straight forward use-cases. What is the vision for tackling more challenging yet useful use-cases? Monads, combinators, etc. Rich Hickey's comments about the pain transducers is causing upon type systems may be another example too. Even Haskell is getting a stiff challenge there.

Thanks!

[jasonkuhrt]

Oh, I forgot to consider in my examples the return value. In Haskell it could be:

add :: Number -> Number -> Number

Which is incredibly simple and concise. I have no idea how flow would do that now or how it would evolve to feature parity from where it stands now. Just seems like its not aiming for this kind of thing but I can always hope I'm wrong about that.

[avikchaudhuri]

Such use cases will probably be handled later in the year as more framework code starts getting converted to Flow.

[wayneseymour]

+1 as I use partial application and currying all the time.

Furthermore, I would be overjoyed if flow supported haskell-ish type signatures in comments.

Pulling from @jasonkuhrt ...if flow could parse:

//: add :: Number -> Number -> Number  
// OR
/*: add :: Number -> Number -> Number */

I would be very much obliged.

For further parsing examples, perhaps consulting @CrossEye or simply the Ramda Docs which have a pull down for each type signature explaining what they do.

[jasonkuhrt]

if flow supported haskell-ish type signatures

I wasn't bold enough to ask this or at least in the context of this issue but I heartily agree that inline type annotations are a mess. It seems many language designers just copy this from the C heritage but to me Haskell Elm Purescript etc. get this way more right.

Inline type annotations present themselves as an after-thought / chore whereas elevated type signatures lend themselves to being in the mindset of a first-class language idea that isn't there to slow you down but actually help design your program, e.g. you can start stubbing out _JUST_ type signatures and iteratively fill out the implementations later without having to get fiddly about it.

Anyways, its off-topic for this issue but and I'm highly pessimistic about this idea in context of the JavaScript community but yeah @wayneseymour totally agree.

[samwgoldman]

I think that add: (a: number) => (b: number) => number is pretty "Haskell-ish," and the function type notation is "properly" right associative, so I think we're pretty good on that front.

As far as currying support, the only issue is varargs, but something like the following works today:

/* @flow */

function add(a: number, b: number): number {
  return a + b;
}

function curry2<A,B,C>(f: (x: A, y: B) => C): (x: A) => (y: B) => C {
  return (a) => (b) => f(a,b)
}

curry2(add)("i")
// test.js|11 col 1 error|  function call
// || Error:
// test.js|11 col 13 error|  string
// || This type is incompatible with
// test.js|3 col 17 error|  number
// || 

[jasonkuhrt]

@samwgoldman I still think there's something to be said about types that stand on their own. Consistency is an essential ergonomic ingredient. Communities standardize on this stuff. e.g. Haskell docs leverage types as the predominant face of documentation https://hackage.haskell.org/package/base-4.7.0.0/docs/Data-Maybe.html#t:Maybe which is a direct mapping of what the user would do in their source code.

As for the currying support I'll try to find time to take another test drive with it and report back.

[samwgoldman]

@jasonkuhrt I'm not sure what you're saying there. By "types that stand on their own" are you referring to your preference for the number -> number -> number syntax over (a: number) => (b: number) => number?

[jasonkuhrt]

@samwgoldman Yes

[jasonkuhrt]

Anyways I'll stop commenting on that aspect since its off topic and super nuanced. Without articulation it can easily appear to not matter.

[samwgoldman]

Cool. In that case, I'm not sure what the remaining issue is. Would you mind restating it?

[jasonkuhrt]

@samwgoldman I want to play with the code you pasted and try other permutations. In particular off the top of my head I want to see how the type of a function changes as its arguments are filled in. If a function takes three arguments and only one is given, it should have a type signature that is a function accepting whatever its remaining rightward args are plus of course the return type. In turn, another function that is compatible with such a function should now accept it, but have rejected it before prior to the first parameter being argued.

[samwgoldman]

OK, it sounds like there really isn't a specific issue here, because flow does support functions that curry (and uncurry) other functions. How do you feel about closing this issue? If you run into something more specific you can always open a new issue.

[jasonkuhrt]

@samwgoldman Yep, just give me a few more hours though because I'm literally diving in right now for the evening.

[jasonkuhrt]

@samwgoldman I was able to break your example here https://github.com/jasonkuhrt/research/blob/master/rough-drafts/typing-javascript.adoc#first-attempt. I worked my way to a correct curry2 implementation and then stopped short of trying to type it for now. That's where I need help and likely where Flow isn't sufficient yet.

So this issue is not resolved and should not be closed.

[samwgoldman]

My curry2 function doesn't attempt to allow passing more than one argument at a time, and extra arguments are ignored by javascript (and therefore flow).

The function you want has two possible return types: either a) the return type of the original function or b) a function that takes more arguments. While it is possible to represent this using a union, it's isn't very fun to use.

/* @flow */

function add(a: number, b: number): number { return a + b }

function sortaCurry2<A,B,C>(f: (a: A, y: B) => C): (x: A, y?: B) => C | (y: B) => C {
  return (a, b) => b ? f(a, b) : (b) => f(a,b)
}

var ex1: number = sortaCurry2(add)(1)(2)
// test2.js|9 col 19 error|  function call
// || Function cannot be called on
// test2.js|3 col 37 error|  number
// || 

This fails because, as far as flow knows, the return type of sortaCurry2(add)(1) is either a function or a number, but it doesn't know which one, because that depends on whether b was passed in and flow can't possibly know that.

Do you see how it is not possible to type this function?

I do not agree that this is a deficiency with flow. I do not think any non-dependently typed language can express this type.

[jasonkuhrt]

and extra arguments are ignored by javascript (and therefore flow)

Ok thanks for confirming what I assumed. So, it would be nice if I could tell flow to be more strict than this; But that's another issue, off-topic.

but it doesn't know which one

Right; this limitation was what I assumed would happen with vanilla Union Types. And this is not surprising since obviously the semantics of currying are simply not modelled by Union Types.

because that depends on whether b was passed in and flow can't possibly know that.
Do you see how it is not possible to type this function?
I do not think any non-dependently typed language can express this type.

So Flow has no plans of exploring being a dependently typed system?

And If no type system can express currying semantics then Haskell must achieve it by "cheating", special-casing currying so that the type system knows how to convert:

  (+) :: Num a => a -> a -> a

into:

  add1 :: Num a => a -> a

@puffnfresh you made a presentation at Strange Loop last year about Idris. I am curious to know your take on bringing typed currying to JavaScript. Possible or impossible even with dependent typing?

Thanks for your patience guys, I'm very new to types and type theory so am being somewhat pedantic!

[samwgoldman]

Haskell doesn't cheat, it just has only one way to apply arguments to functions, which is one-at-a-time. One way to represent multiple-argument functions in JS is using Haskell's tuples, like so:

JS (a: number, b: number) => number is like Haskell Num a => (a, a) -> a
JS (a: number) => (b: number) => number is like Haskell Num a => a -> a -> a

My first curry2 function takes the first type to the second type. Indeed, Haskell has a curry function that does the same thing.

Does that help?

[jasonkuhrt]

@samwgoldman Ah, thank-you it does help. So it is just Haskell's syntax that makes it appear like multiple arguments are given at at a time, e.g. these are actually invoked _identically_:

Prelude> (+) 1 2
3
Prelude> (+)(1)(2)
3

And the un-curried version in Haskell actually (as you suggested for the JS representation) accepts still one argument, but a tuple, itself finally actually holding the n arguments:

Prelude> (uncurry (+)) (1,2)
3

Ugh, translating how this works to JavaScript results in a poor UX for the JS user, since the assumptions either language makes lends to syntax optimized for opposing idioms. Every JS function would be allowed to either be invoked multiple times or given an array of remaining params. But additional confusion would arise for JS functions with literal array-typed parameters... leading to a crazy system of custom tuple-argument data type:

add(1)(2)

or:

add(argTuple(1, 2))

Ergonomically unacceptable.

But, then would the system be constrained enough for a type system to statically check?

Getting sweet.js involved would potentially alleviate the ergonomic issue but it would require radically changing the language such that inter-op would be hard or impossible (e.g. turn every multi-argument function into a tuple form).

@samwgoldman Thanks again for explaining this stuff.

[samwgoldman]

So, given all of the above, can we agree there is no issue with flow here?

[jasonkuhrt]

Yeah I think so, to the best of my knowledge I cannot suggest otherwise. I'm disappointed, but just in general, not with Flow specifically ; )

[jgrund]

It's a bummer that flow cannot express curried functions in the way they are currently implemented in the JS ecosystem (see: http://ramdajs.com/0.19.1/docs/#curry, https://lodash.com/docs#curry).

I imagine it's even more difficult once you factor in things like placeholder arguments.

If you could denote a type to not ignore extra args, would that at least help with union (intersection?) types?

[rpominov]

This seems to be possible in TypeScript, see https://github.com/donnut/typescript-ramda/
Can something similar be done with Flow?

[samwgoldman]

@rpominov If you look at the type definitions there, you'll see that specific arities are typed via overloads, then a generic fallback type is provided. Yes. this is also possible in Flow.

[krainboltgreene]

One example that isn't listed here as far as I can tell (and is becoming more common):

// file: InsertFromModel/index.js

import {pipe} from "sanctuary" // or ramda
import {asAttributes} from "model"
import {asInsert} from "sql"

export default pipe(
  [
    // Object
    asAttributes,
    // [Object, n]
    asInsert,
    // ["INSERT ...", n]
  ]
)

Currently there's nothing really to hook into for type declarations, and even when you have that it doesn't "quite" work:

const InsertFromModel: Function = pipe(
  [
    // Object
    asAttributes,
    // [Object, n]
    asInsert,
    // ["INSERT ...", n]
  ]
)

While technically true, it's not helpful. I know pipe is a function, what I would love to do is asser that it returns Array<string>.

[c089]

@krainboltgreene I think you could use const InsertFromModel: () => [string] = pipe( here.

[gcanti]

@jgrund @rpominov flow can definitely express curried functions, even the JavaScript flavour, see here

https://github.com/gcanti/flow-static-land/blob/master/src/Fun.js#L26

or here

https://github.com/flowtype/flow-typed/blob/master/definitions/npm/ramda_v0.21.x/flow_%3E%3Dv0.28.x_%3C%3Dv0.29.x/ramda_v0.21.x.js#L25

@samwgoldman can this be closed? Someone pointed me to this issue, he thought there was no (or bad) support for currying

[rpominov]

@gcanti Perhaps the only problem at this moment is that overloading isn't supported for class methods #2260 (in implementation file, it's supported in declarations).

But yeah, this issue can be closed I think.

[jgrund]

Yes, this is possible to model with intersections. It started to work reliably when intersections / unions were overhauled.

I have also done an implementation that uses placeholders which also works at the cost of more overload permutations.

I agree this can be closed.

[deoqc]

Even thought it is possible to express currying with overloading like @gcanti showed clearly here, currying does not seem a first-class feature and this approach may be fragile / error prone (or maybe even say has bad support).

Could not considerer adding currying as fully supported, since it is such important feature and getting more ubiquitous, instead of having to provide several overloading signatures?

[kevinbarabash]

In addition to currying, being able to have type information flow through compose and pipe so that they produce methods that flow knows the type of without having to manually provide that information would go along way in supporting functional programming.

type fn = (v: any) => any;
const compose = (...fns: fn[]): fn => x => fns.reduceRight((v, f: fn) => f(v), x);

const add5 = (a: number): number => a + 5;
const str = (a: number): string => a.toString();

const foo = compose(str, add5);
const bar = (compose(str, add5) : (v: number) => string);

const print = (num: number) => console.log(num);

print(foo(5));  // no error
print(bar(5));  // errors

[gcanti]

@kevinbarabash here you can find some typings for curry, compose and pipe

import { compose } from 'flow-static-land/lib/Fun'

const add5 = (a: number): number => a + 5
const str = (a: number): string => a.toString()
const foo = compose(str, add5)

const print = (num: number) => console.log(num)

print(foo(5)) // error: string. This type is incompatible with number

[kevinbarabash]

I wish we had a more elegant way of describing composition. The nice thing about those typings is that they enforce that the return type of the previous function is the param type of the following function.

[nmn]

Seems like a settled issue that everyone is OK with closing. There are some good feature requests that are covered elsewhere.

[StreetStrider]

@gcanti, hello. Interesting package. I wonder, had you an idea to implement a macro or something to render this multi-signature functions automatically? And, in general, is there any efforts (somewhere) to supply macroses to some features that not present in Flow?

[nmn]

@StreetStrider Flow is not a compiler. All type definitions make no actual difference to the actual code that will be run. And the Babel transform will literally strip those types. So It cannot support macros.

However, there are a few Utility types in Flow that make it easier to write your own type definitions. There is also some Utility Types you can create on your own.

[StreetStrider]

@nmn I wasn't saying Flow is a compiler. I meant «precompiler/macroses for Flow itself», to get rid of things such as this crazyness.

[nmn]

@StreetStrider Oh, I see. I see the value in that, but I don't think that will happen any time soon.
There are some other options that are being considered that may make the situation a little better.

[StreetStrider]

@nmn, agree. This task is complex, indeed. I think for future it will be good for Flow to have some form of algebra that allows following features and operations:

1. Variadic generic arg that can be then passed to function signature and will be treated as a whole type, like a «signature».
2. Slicing of signatures. This would allow to define curry, for instance.
3. Concatting of signatures. e.g. for bind.
4. Retrieving signature and retval from function type (it's like head and tail for sequences). e.g. for promisify.
5. …maybe other operations.

As for my question to gcanti, I was asking just for workaround to eliminate this signature ladders for now. Maybe someone works on some simple pre-renderer that will do the trick. Flow development is slow-paced, this would be good to know about any enthusiasts working on Flow independently.

[nmn]

All of that sounds great. Flow is still early in its development cycle and it started with a pretty complex and expressive type system. The problem with signature ladders is common in other languages like Swift too.

I'm sure things can improve but I don't think that it's the most pressing issue for Flow right now.