Proposal: specs for Maybe, Either, Tuple, Task, ... #185
Comments
|
Just as another example: a spec for Maybe could be used for |
|
Having used I'm not totally sold on a whole spec for either as they type should say enough? |
|
You can use Either and before returning it just do About // unfoldr :: (Unfoldable t) => (((a, b) -> c, c, b) -> c) -> b -> t a
List.unfoldr((next, done, x) => x > 100 ? done : next(x*x, x+1), 0)Also for example // chainRecWithEither :: (ChainRec m) => (TypRep m, a -> m (Either a r), a) -> m r
const chainRecWithEither = (T,f,i) => T.chainRec(
(next,done,x) => f(x).map(e => e.fold(next,done)),
i
)Also using |
|
Thanks @safareli some food for thought 👍 |
|
Good point about ambiguous meaning of Left and Right in chainRec. Maybe we could have some general spec that would describe APIs of sum and product types? Something like a spec for daggy's |
Some sketch of ideas: // Step a b = Loop a | Done b
Step.types = ['Loop', 'Done']
Step.Loop = (a) => ({
type: Step.types[0],
constructor: Step,
values: { _1: a },
keys: ['_1'],
})
Step.Done = (a) => ({
type: Step.types[1],
constructor: Step,
values: { _1: a },
keys: ['_1'],
})
// Maybe a = Nothing | Just a
Maybe.types = ['Nothing', 'Just']
Maybe.Just = (a) => ({
type: Maybe.types[1],
constructor: Maybe,
values: { _1: a },
keys: ['_1'],
})
Maybe.Nothing = {
type: Maybe.types[0]
constructor: Maybe,
values: {},
keys: [],
}
// List a = Nil | Cons a (List a)
List.types = ['Nil', 'Cons']
List.Cons = (a, b) => ({
type: List.types[1],
constructor: List,
values: { _1: a, _2: b },
keys: ['_1', '_2'],
})
List.Nil = {
type: List.types[0],
constructor: List,
values: {},
keys: [],
}
// Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)
Tree.types = ['Empty', 'Leaf', 'Node']
Tree.Node = (a, b, c) => ({
type: Tree.types[2],
constructor: Tree,
values: { _1: a, _2: b , _3: c },
keys: ['_1', '_2', '_3'],
})
Tree.Leaf = (a) => ({
type: Tree.types[1],
constructor: Tree,
values: { _1: a },
keys: ['_1'],
})
Tree.Empty = {
type: Tree.types[0],
constructor: Tree,
values: {},
keys: [],
}using const valuesAsArray = v => {
let args = []
for (var i = 0; i < v.keys.length; i++) {
args.push(v.values[v.keys[i]])
}
return args
}
const fold = (fs, v) => {
const idx = v.constructor.types.indexOf(v.type)
if(idx == -1) throw new TypeError('invalid value')
return fs[idx](...valuesAsArray(v))
}
const cata = (fs, v) => fs[v.type](...valuesAsArray(v))
// we can also check if `fs` does not contain functions for all `v.constructor.types`
//
// `keys` from instance could be moved to to Type, e.g.:
// Tree.typeNames = ['Empty', 'Leaf', 'Node']
// Tree.typeKeys = [
// [],
// ['_1'],
// ['_1', '_2', '_3'],
// ]
// |
Some good comments by @robotlolita and @SimonRichardson on that in #154 |
|
I'm not sure the spec describing specific data structures is a good idea, but as far as the description of tagged unions goes, something like OCaml's (and Lamdu's) Open Variants may be considered. |
Let me try to provide more motivation for my decision. I've found that if you type This is especially noticeable in PureScript because the If you break the recursion up into smaller functions and try to compose your functions, you end up having to complicate the problem a bit in order for things to line up. This is why If you have foo = tailRec go
where
go x = do
y <- bar x
z <- baz y
Left ("Barring " <> show x <> " with a bazzed " <> show y <> " gives " <> show z)Whereas, with foo = tailRec go
where
go x =
case bar x of
Right b ->
Right b
Left y ->
case baz y of
Right b ->
Right b
Left z ->
Right ("Barring " <> show x <> " with a bazzed " <> show y <> " gives " <> show z)But, that's just using As far as The point I wish to get across is that we don't get much benefit from renaming each value constructor. It might look prettier, but it's also demonstrably more difficult to use. We get a good deal more if you line up the type variables to play better with our |
|
It pains me that we even have to question whether it's valuable to talk about Also, how does this function work: chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m bWhere do you get the |
|
I can't think of any cases where |
This actually follows from the algebraic types algebra:
So pair of functions Not sure if this helps, I just though it's cool to mention 😄 |
|
As always @joneshf you put it way better than me... |
|
I hope that didn't come off negative. I'm not upset with any of the choices or comments anyone has made. |
|
I found it very informative 😀 |
|
I think I vote for Church-encoding, because specifying data types seems no different to just providing an implementation. Main problem I see is that lots of data types can not be encoded without talking about existential types, including this case. It seems like chainRec :: ChainRec m => (a -> m (forall c. (a -> c) -> (b -> c) -> c)) -> a -> m b |
why? |
Maybe an interface? // just a sketch
interface Either<L, R> {
left<L, R>(left: L): Either<L, R>;
right<L, R>(right: R): Either<L, R>;
isLeft(): boolean;
isRight(): boolean;
fromLeft(): L;
fromRight(): R;
of...
map...
ap...
chain...
} |
|
I don't think an interface is a good idea either. |
|
We would need to have at least interface + some laws I think. |
|
If we want to represent unions and cartesian products in a way that can be manipulated by JavaScript, but hiding the concrete implementation, doesn't mean we have to define functions, and then group them in interfaces? interface Union2<A, B> {
// constructors
a(): Union2<A, B>;
b(): Union2<A, B>;
isA(): boolean;
fromA(): A; // fromA(a(x)) = x
isB(): boolean;
fromB(): B; // fromB(b(x)) = x
}
interface Union3<A, B, C> {
a(): Union3<A, B, C>;
b(): Union3<A, B, C>;
c(): Union3<A, B, C>;
isA(): boolean;
fromA(): A;
isB(): boolean;
fromB(): B;
isC(): boolean;
fromC(): C;
}
...etc...
interface Product2<A, B> {
// constructor
make(a: A, b: B): Product2<A, B>;
// projections
prjA(): A; // projA(make(x, y)) = x
prjB(): B; // projB(make(x, y)) = y
}
...etc...https://github.com/purescript/purescript-either/blob/master/src/Data/Either.purs#L228-L243 |
|
@gcanti those data-types can be Church-encoded (pedantically, Boehm-Berarducci encoded, if we're using types) meaning they can be represented as functions. type Maybe a = forall b. b -> (a -> b) -> b
type Either a b = forall c. (a -> c) -> (b -> c) -> cfunction nothing(b, f) {
return b;
}
function just(a) {
return function(b, f) {
return f(a);
};
}
function left(a) {
return function(l, r) {
return l(a);
};
}
function right(b) {
return function(l, r) {
return r(b);
};
}
// Example
function eitherToMaybe(e) {
return e(
function(ignored) { return nothing; },
just
);
} |
That makes more sense. |
|
@puffnfresh Yes, and it's a really interesting topic, but my point is (and I understand if you don't agree):
I'd prefer to not handle Church-encoded data-types in my code, if possible. I'd love to manipulate plain old Though maybe I'm off the track and in practice is not a problem at all |
|
I am in favour of Church/BB encoding. My normal solution to the "unfriendliness" would be to additionally expose friendly helpers, but that seems harder in the case of a spec. Also, I don't see why you can't have chainRec :: ChainRec m => (forall c. (a -> c, b -> c, a) -> m c, a) -> m band then the |
|
The If you could get rid of it, you'd be tasked with somehow finding a useful function You can try implementing it in PureScript or Haskell if you'd like to see where it fails. The easiest data type to implement it for would be PureScript import Prelude
import Data.Identity
class Bind f <= ChainRec f where
chainRec :: forall a b c. ((a -> c) -> (b -> c) -> a -> m c) -> a -> m b
instance chainRecIdentity :: ChainRec Identity where
...Haskell class Monad f => ChainRec f where
chainRec :: ((a -> c) -> (b -> c) -> a -> m c) -> a -> m b
instance ChainRec Identity where
...Or just try to write it in flow/typescript if that's your thing. |
|
Thanks, Hardy, that's really useful!
Can you point me to somewhere to learn about that? |
|
Looks like I had the quantification rules exactly backwards. I was thinking scopes on the left could be extended across the whole of the right, but scopes on the right could not be extended to the left. This appears to be almost opposite to the actual case (barring name collisions). I guess I would phrase my understanding of why this happens as "you lose necessary polymorphism if you extend the scope to the right" |
|
I don't think precluding |
|
A quick comment about the It feels weird. The way I would expect to find out if the value I got is a Just or a Nothing (or a Left or Right in an Either for that matter) is to case-split on it, not to check the value of a property. I feels clean how FL specs only talk about functions right now. Wouldn't it be viable to go in the direction of x.cata({
Just: value => console.log(value),
Nothing: () => console.log('It was a Nothing')
})? |
You're absolutely right, Simon! I agree that this is quite clean, @xaviervia: Maybe.prototype.cata :: Maybe a ~> { Nothing :: () -> b, Just :: a -> b } -> bI consider this to be even cleaner: Maybe.maybe :: b -> (a -> b) -> Maybe a -> bThe advantage is that there are no labels. Those who prefer to think of “Some” and “None” rather than “Just” and “Nothing” are free to do so. Specifying as little as possible seems wise. For this reason perhaps we should specify that the folding function on the type representative be named |
|
So maybe I think specifying a pattern matching like function results in a very nice API. But I also see some downsides.
I'd like for the Fantasy Land spec not to have a performance penalty. Requiring |
Perhaps not, although it does expose the tag name.
The function needn't be curried. I believe Gabe was considering usability, but one could expose a separate function for public use: Maybe["fantasy-land/fold"] :: (b, a -> b, Maybe a) -> b
Maybe.maybe :: b -> (a -> b) -> Maybe a -> b |
you could declare folding functions/values at the top level of your file, so they do not close over some values. and then use them to covert the maybe into some inspectable form and use it so no closure allocation is needed and only overhead is calling a function + constructing resulting object or whatever this folding functions return. if you are concerting them to some specific maybe type you can first check if it's instance of that type in which case you do not need to call cata/fold/.. on it |
But
There should be no specification that an ADT implement any of the FL algebras.
-- These
This :: a -> These a b
That :: b -> These a b
These :: a -> b -> These a bWhich flags should we choose? These.cata :: (a -> c) -> (b -> c) -> (a -> b -> c) -> c
Also, avoiding a folding function would require specifying either This proposal isn't meant to be restrictive. Library authors are free to implement any other functions/methods/properties they want. And they don't have to be built on top of the folding function. @xaviervia, @davidchambers
|
|
... Because I got pinged: I like the Church idea, but could be convinced of formalising const Just = x => _ => f => f(x)
const Nothing = x => _ => xAnything else (again, with the possible exception of a 🏃 |
Who is providing |
|
The Maybe is the folding function :D You don't have to "get" anywhere if everything is done on primitive Church encoding. Leave the library to find pretty words for things, but the spec to encode the bare necessities. |
Aha! I see it now. Very cool!
Requiring Church encoding seems problematic to me. As @paldepind observed, Church-encoded ADTs cannot provide |
|
I feel like we're getting close. How about a function or method which transforms the value into it's Church-encoded representation? maybe :: Maybe a ~> b -> (a -> b) -> bMyLib.Just(42).maybe (OtherLib.None) (OtherLib.Some) |
Functions are objects and/mutate props on them. I'm not saying that we should use one church encoded maybe tho. If a maybe is implemented using church encoding it might overflow stack on some operations, like this: instance Functor ChurchMaybe where
fmap f (ChurchMaybe x) = ChurchMaybe $ \n j -> x n (j . f) |
I completely agree. Specifying that the
I think that is a good idea. It is almost the same as what David suggested except the method lives directly on the
That is not what I meant. My point was just that the various specifications should be compatible with each other. But, now that you're stating it, I'm wondering: why not? If we did specify that |
Yes, you're right that |
@paldepind having a Array.prototype['fantasy-land/maybe'] = function (x, f) {
return this.length === 0 ? x : f(this[0]);
}
var safeHead = m => m['fantasy-land/maybe'](Nothing, Just);
safeHead([]) // Nothing
safeHead([42]) // Just(42)A specification for MaybeThe If
maybe method
A value which conforms to the m.maybe(x, f)
|
|
@gabejohnson 👍 Array example peaty nice |
|
It's been brought to my attention that function (d, f) {
return this.reduce((_, x) => f(x), d);
}This satisfies the signature. For Edit: swapped parameters. |
|
It's because any Foldable element can be folded into an Array |
|
Alright, I'll ask it: why is this the hill we're willing to die on?
By NOT providing an My vote is to just define |
|
What is the consequence of any particular spec for Maybe for other ADTs? Any definition of Maybe will work as the template of how other ADTs should be defined in FL, if the time comes when they are added. Either is a great example. Thinking about the proposal of having m.either(f, g)where both Will l.list(x, f)where It will seem the consistent thing to do from the proposal of It would seem that naming the functions after the types ( |
|
@xaviervia Array.prototype['fantasy-land/list'] = function list(f, d) {
return this.length === 0
? d
: f(this[0], this.slice(1).list(f, d));
}; |
|
I see! While writing the examples I wondered if some of them would be redundant, at least one was :D Is this something you find interesting then? I have limited experience with pure FP languages so I cannot of the top of my head picture if there would be an obvious limitation to this kind of "pattern matching" (especially one that would not also happen with the And thinking out loud (no need to answer): I wondered in the past what was the reason that FL did not specify any sort of type constructor case analysis, and my guess was that case analysis was not an algebra like the other ones, but seeing how this function-flavored case analysis would work I'm starting to second guess that assumption. Maybe the way type structure is managed in statically typed languages is a convention / arbitrary decision and not something that "just is"? |
|
I don't want to derail the conversation on #281, and I've been quite out of the loop, but originally the idea of adding particular data structures to the specification was just simplifying the type signatures. It seems like the current purpose is much broader than that, though. Trying to define data structures that work across different implementations is not a good idea. There's no need to have different representations for data structures within Fantasy Land (because the functions don't care). But having this possibility opens the possibility of problems that are hard to predict/debug: what if something tries to call a method that isn't defined in fantasy land? What if the method is actually there but does something the user didn't expect? What happens if multiple libraries define an It's just too many potential problems for little benefit. If we're going to add data structures to the spec, I'll agree with @joneshf (if I understood the comment correctly) and say we should just implement the data structures in Fantasy Land, we could even have a fantasy-land-runtime library that provides operations on those values. It'll be simpler and far more predictable. Users will know exactly what's in the object they get from all fantasy land functions, and if they really need it they can pay the price of converting that to a specific library representation (libraries can implement a "fromFantasyLandEither(foo)" method or whatever). A specification could be as simple as: type Maybe a =
{ tag: "Nothing" }
| { tag: "Just", value: a } |
|
@robotlolita I've made some changes to #280 that would make interop very simple. That being said, I think any specification is better than none.
Agreed. In fact, why have more than one ADT library? Currently we have:
And these are just the libraries in the Fantasy Land ecosystem. There seems to be a lot of duplicated effort. @robotlolita a simple spec, as you mentioned above, could be implemented once using daggy (with contributions from all interested lib authors/maintainers). I've noticed a lot of confusion amongst those new to FL concerning where they should get their data types. It creates an unnecessary barrier to entry for beginners and hurts the ecosystem as a whole. I'm not saying every data type should come from this org, but the basic ones are so simple there's no good reason to do so repeatedly. |
I'm a big fan of always having a marketplace of ideas. I think it's this competition that spurs us to improve. |
I consider sanctuary-type-classes to be this library. I don't know whether others share this view. |
|
Should Option/Maybe be strict or lazy? If you specify one, you're making this decision for everyone. |
Sorry if it was discussed before, after scanning the issues I didn't find anything on the subject.
The motivation comes from the last addition: the spec for
chainRecwhich I find hard to understandwith respect to
Relevant issues
I understand the benefits of not depending on a particular implementation of
Eitherbut why fantasy-land doesn't provide a spec forEitherin the first place?For example writing the spec for
Unfoldablewould be problematic (MaybeANDTuple)We have great libraries out there for
Maybe,Either,Task, etc... but there's no standard for them.Would it be a good idea to add specs for these concrete types?
The text was updated successfully, but these errors were encountered: