6 ms·

This post shows a Haskell-ish definition of Functor, then attempts to show the same thing in TypeScript. interface Functor<A> { map(f: (a: A) =>

by evmar 7y ago

This post shows a Haskell-ish definition of Functor, then attempts to show the same thing in TypeScript. interface Functor<A> { map(f: (a: A) => B): Functor; } But the TypeScript definition loses something important: the point of a Functor is that you get back the same data type -- there's one `f` in the Haskell defn both in the argument and return type, while this TS definition can give you back any random data type. E.g. the implementation of Array.map could give you back an Either. I don't mean this comment to be a random nitpick of the post. Trying to think these things through is hard, and trying to use things you know to help understand the new idea is not unreasonable. But in particular with PL each thing has so much associated baggage (here in TS, subtyping) that reasoning "by metaphor" often means you end up missing the critical point.

gcanti 7y ago
fp-ts [1] contains an implementation of Higher Kinded Types, which TypeScript doesn’t support natively (the idea for emulating higher kinded types in TypeScript is based on "Lightweight higher-kinded polymorphism" [2]) [1] https://github.com/gcanti/fp-ts https://github.com/gcanti/fp-ts [2] https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphism.pdf https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-ki...
lacampbell 7y ago
Haven't had a coffee yet so go easy on me - doesn't this solve your issue? interface Functor<A> { map(f: (a: A) => A): Functor<A>; } You map over an option, you get an option. You map over an either, you get an either. etc etc.
- tel 7y ago
 That gets closer to the problem, but the solution is further away. You don't want to return "Functor" (which is like a vtable, the interface itself) but instead the thing itself which is implementing the Functor interface. So you end up with interface Functor<A> { map(f: (a: A) => A): Self } where `Self` needs to recognize that the type being defined to implement this interface has a "slot". This tends to make things tough.
 - lacampbell 7y ago
 You've lost me. Returning an interface isn't returning a concrete thing. It's returning the thing that implements the interface I'm a very low level functional programmer. I'm big on immutability, big on not using loops and instead using map/flatMap/filter/fold, I tend to roll my own either and option implementations when they don't exist because it's the tidiest way of handling errors I've come across, etc etc. But when it comes to stuff like functors I don't get what it's buying me. What interesting stuff can I do if I know that both an option and a list can be mapped over? I really need to look more deeply into it at some stage. I might be missing out on some powerful tools. Or it might be a bunch of stuff that's theoretically interesting but practically useless.
 - rockostrich 7y ago
 I think you may have misunderstood their point. They're just saying that specifying `Functor` in the return type of `map` isn't enough to resolve the issue because you could still have a case of `List#map` returning a `Maybe` or `Either` since they are all implementations of `Functor`. This gets handle by the Cats library in Scala (https://typelevel.org/cats/typeclasses/functor.html https://typelevel.org/cats/typeclasses/functor.html) by defining the type class the functor is being defined for as an abstract type on the functor itself.
 - tel 7y ago
 Sorry, you're right. I wasn't thinking with subtyping. Rockostrich demonstrated the other weakness of this approach, but I'll say it outright: if you return a supertype then you've lost information. It's very important for the type of `fmap f x` to be identical to `x` except in that its "inner" type has been modified. Without that, these kinds of interfaces lose all of their value.
 - rubyn00bie 7y ago
 I'd like to +1 that "tends to make things tough." Not sure how it is today, I think it was remedied in Swift 4.1 or something... but holy-shit, that "slot" problem gave me endless grief trying to implement functors in swift for composing UI structs (I was ahead of the curve, heh).
- smegma2 7y ago
 The functor it returns should be the same functor it was called on, i.e. calling map on a Maybe should return a Maybe. The parameterized type can change so map can bring you from a Maybe<Int> to a Maybe<String> which is why in the above description we have Functor instead of A. But what typescript is lacking is a way to describe that the functor returned should be the same.
crimsonalucard 7y ago
Actually both the Haskell and type script definitions don't communicate the concept of a functor well. Especially with the way it's used. The interface only requires you to implement the mapping between morphisms, but a mathematical functor also includes mappings between the objects from one category to the next. Additionally fmap is actually mapping (a -> b) to (f a -> f b) but the way it's typically used in haskell breaks this intuition. Most people see it as ((a -> b), f a) to (f b) as a result of how it's used in FP. Technically the usages are isomorphic but using it this way blocks your intuition from fully understanding the true nature of a functor. The following would be more a more accurate type class for a functor: class Functor f where fmap :: (a -> b) -> (f a -> f b) tmap :: a -> f a See here: https://en.wikipedia.org/wiki/Functor https://en.wikipedia.org/wiki/Functor Note that there are TWO axioms for functor, I added the second axiom to complete the definition. I think the reason why tmap doesn't exist is because it's trivial? Not sure maybe some expert can pitch in as I'm certainly not an expert in haskell.
- kmill 7y ago
  Functors don't include tmap. Yes, a functor maps objects from one category to objects of the second, but it does so on the sets of objects. There might not be a corresponding morphism between "a" and "f a". The typeclass you created would be a functor along with a natural transformation from the identity functor to f. I don't think these always exist, but they do for applicative functors (pure/return). The object mapping is reflected at the type level. "f a" is the object that "f" sends "a" to. In Haskell, functors are all endofunctors. In math, functors can be between categories, and in such a case a -> f a might not make any sense because there are no morphisms between categories. Using some quasi-Agda syntax, here would be a full definition of a functor between two categories. Maybe you could overload "->" so that "X -> Y" could mean "Mor X Y" for the set of morphisms between X and Y in C or D (depending on context). Curly brackets mean optional parameters, which Haskell approximates via typeclasses. record Functor where field C, D : Cat F : Ob C -> Ob D fmap : {X Y : Ob C} -> Mor{C} X Y -> Mor{D} (F X) (F Y) fmapId : {X : Ob C} -> fmap id == id fmapComp : {X Y Z : Ob C} -> {f : Mor X Y} -> {g : Mor Y Z} -> fmap g . fmap f == fmap (g . f)

by evmar 7y ago

gcanti 7y ago

fp-ts [1] contains an implementation of Higher Kinded Types, which TypeScript doesn’t support natively (the idea for emulating higher kinded types in TypeScript is based on "Lightweight higher-kinded polymorphism" [2]) [1] https://github.com/gcanti/fp-ts https://github.com/gcanti/fp-ts [2] https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphism.pdf https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-ki...

lacampbell 7y ago

Haven't had a coffee yet so go easy on me - doesn't this solve your issue? interface Functor<A> { map(f: (a: A) => A): Functor<A>; } You map over an option, you get an option. You map over an either, you get an either. etc etc.

tel 7y ago
That gets closer to the problem, but the solution is further away. You don't want to return "Functor" (which is like a vtable, the interface itself) but instead the thing itself which is implementing the Functor interface. So you end up with interface Functor<A> { map(f: (a: A) => A): Self } where `Self` needs to recognize that the type being defined to implement this interface has a "slot". This tends to make things tough.
- lacampbell 7y ago
 You've lost me. Returning an interface isn't returning a concrete thing. It's returning the thing that implements the interface I'm a very low level functional programmer. I'm big on immutability, big on not using loops and instead using map/flatMap/filter/fold, I tend to roll my own either and option implementations when they don't exist because it's the tidiest way of handling errors I've come across, etc etc. But when it comes to stuff like functors I don't get what it's buying me. What interesting stuff can I do if I know that both an option and a list can be mapped over? I really need to look more deeply into it at some stage. I might be missing out on some powerful tools. Or it might be a bunch of stuff that's theoretically interesting but practically useless.
 - rockostrich 7y ago
 I think you may have misunderstood their point. They're just saying that specifying `Functor` in the return type of `map` isn't enough to resolve the issue because you could still have a case of `List#map` returning a `Maybe` or `Either` since they are all implementations of `Functor`. This gets handle by the Cats library in Scala (https://typelevel.org/cats/typeclasses/functor.html https://typelevel.org/cats/typeclasses/functor.html) by defining the type class the functor is being defined for as an abstract type on the functor itself.
 - tel 7y ago
 Sorry, you're right. I wasn't thinking with subtyping. Rockostrich demonstrated the other weakness of this approach, but I'll say it outright: if you return a supertype then you've lost information. It's very important for the type of `fmap f x` to be identical to `x` except in that its "inner" type has been modified. Without that, these kinds of interfaces lose all of their value.
- rubyn00bie 7y ago
 I'd like to +1 that "tends to make things tough." Not sure how it is today, I think it was remedied in Swift 4.1 or something... but holy-shit, that "slot" problem gave me endless grief trying to implement functors in swift for composing UI structs (I was ahead of the curve, heh).
smegma2 7y ago
The functor it returns should be the same functor it was called on, i.e. calling map on a Maybe should return a Maybe. The parameterized type can change so map can bring you from a Maybe<Int> to a Maybe<String> which is why in the above description we have Functor instead of A. But what typescript is lacking is a way to describe that the functor returned should be the same.

crimsonalucard 7y ago

Actually both the Haskell and type script definitions don't communicate the concept of a functor well. Especially with the way it's used. The interface only requires you to implement the mapping between morphisms, but a mathematical functor also includes mappings between the objects from one category to the next. Additionally fmap is actually mapping (a -> b) to (f a -> f b) but the way it's typically used in haskell breaks this intuition. Most people see it as ((a -> b), f a) to (f b) as a result of how it's used in FP. Technically the usages are isomorphic but using it this way blocks your intuition from fully understanding the true nature of a functor. The following would be more a more accurate type class for a functor: class Functor f where fmap :: (a -> b) -> (f a -> f b) tmap :: a -> f a See here: https://en.wikipedia.org/wiki/Functor https://en.wikipedia.org/wiki/Functor Note that there are TWO axioms for functor, I added the second axiom to complete the definition. I think the reason why tmap doesn't exist is because it's trivial? Not sure maybe some expert can pitch in as I'm certainly not an expert in haskell.

kmill 7y ago
Functors don't include tmap. Yes, a functor maps objects from one category to objects of the second, but it does so on the sets of objects. There might not be a corresponding morphism between "a" and "f a". The typeclass you created would be a functor along with a natural transformation from the identity functor to f. I don't think these always exist, but they do for applicative functors (pure/return). The object mapping is reflected at the type level. "f a" is the object that "f" sends "a" to. In Haskell, functors are all endofunctors. In math, functors can be between categories, and in such a case a -> f a might not make any sense because there are no morphisms between categories. Using some quasi-Agda syntax, here would be a full definition of a functor between two categories. Maybe you could overload "->" so that "X -> Y" could mean "Mor X Y" for the set of morphisms between X and Y in C or D (depending on context). Curly brackets mean optional parameters, which Haskell approximates via typeclasses. record Functor where field C, D : Cat F : Ob C -> Ob D fmap : {X Y : Ob C} -> Mor{C} X Y -> Mor{D} (F X) (F Y) fmapId : {X : Ob C} -> fmap id == id fmapComp : {X Y Z : Ob C} -> {f : Mor X Y} -> {g : Mor Y Z} -> fmap g . fmap f == fmap (g . f)

This post shows a Haskell-ish definition of Functor, then attempts to show the same thing in TypeScript. interface Functor<A> { map<B>(f: (a: A) =>

This post shows a Haskell-ish definition of Functor, then attempts to show the same thing in TypeScript. interface Functor<A> { map<B>(f: (a: A) =>