search

fantasyland / fantasy-land

Specification for interoperability of common algebraic structures in JavaScript
MIT License
10.13k stars 376 forks source link

Strong #276

Open puffnfresh opened 7 years ago

puffnfresh commented 7 years ago

Instead of Arrow (#273) we should have Strong Profunctor. It probably makes sense to do Choice Profunctor with this.

The occurrences of Tuple and Either should be Scott-encoded so we don't have to directly specify data types.

safareli commented 7 years ago

Is Scott encoding same as Church encoding? if not what's the difference

CrossEye commented 7 years ago

I'm an atheist and not involved in Church encoding.

-- Scott

puffnfresh commented 7 years ago

@safareli there's an awesome paper on this:

https://ifl2014.github.io/submissions/ifl2014_submission_13.pdf

Church:

2017-10-27-070919_391x140_scrot

Scott:

2017-10-27-070926_334x108_scrot

paldepind commented 7 years ago

The occurrences of Tuple and Either should be Scott-encoded so we don't have to directly specify data types.

I think using an object encoding is more appropriate for JavaScript. See my comment here for a rationale.

safareli commented 7 years ago

@puffnfresh for non recursive data types both Church and Scott encoding would be same right?

ivenmarquardt commented 6 years ago

I'd love to see Scott encoded ADTs in FL. Javascript has multi argument functions, so products are for free.

@safareli Yes, both are implemented as continuations. Scott uses functional pattern matching (uncons) to deconstruct recursive types, whereas Church uses a catamorphism (foldr). As a result Scott has explicit recursion (at the type and value level) and Church implicit.