98

I've been doing dev in F# for a while and I like it. However one buzzword I know doesn't exist in F# is higher-kinded types. I've read material on higher-kinded types, and I think I understand their definition. I'm just not sure why they're useful. Can someone provide some examples of what higher-kinded types make easy in Scala or Haskell, that require workarounds in F#? Also for these examples, what would the workarounds be without higher-kinded types (or vice-versa in F#)? Maybe I'm just so used to working around it that I don't notice the absence of that feature.

(I think) I get that instead of myList |> List.map f or myList |> Seq.map f |> Seq.toList higher kinded types allow you to simply write myList |> map f and it'll return a List. That's great (assuming it's correct), but seems kind of petty? (And couldn't it be done simply by allowing function overloading?) I usually convert to Seq anyway and then I can convert to whatever I want afterwards. Again, maybe I'm just too used to working around it. But is there any example where higher-kinded types really saves you either in keystrokes or in type safety?

5
  • 2
    Many of the functions in Control.Monad make use of higher kinds so you might want to look there for some examples. In F# the implementations would have to be repeated for each concrete monad type.
    – Lee
    Commented Jan 16, 2014 at 19:16
  • 1
    @Lee but couldn't you just make an interface IMonad<T> and then cast it back to e.g. IEnumerable<int> or IObservable<int> when you're done? Is this all just to avoid casting?
    – lobsterism
    Commented Jan 16, 2014 at 19:49
  • 4
    Well casting is unsafe, so that answers your question about type safety. Another issue is how return would work since that really belongs to the monad type, not a particular instance so you wouldn't want to put it in the IMonad interface at all.
    – Lee
    Commented Jan 16, 2014 at 20:07
  • 4
    @Lee yeah I was just thinking you'd have to cast the final result after the expression, no biggie because you just made the expression so you know the type. But it looks like you'd have to cast inside each impl of bind aka SelectMany etc too. Which means someone could use the API to bind an IObservable to an IEnumerable and assume it would work, which yeah yuck if that's the case and there's no way around that. Just not 100% sure there's no way around it.
    – lobsterism
    Commented Jan 16, 2014 at 20:29
  • 6
    Great question. I've yet to see a single compelling practical example of this language feature being useful IRL.
    – J D
    Commented Sep 26, 2015 at 11:45

7 Answers 7

89

So the kind of a type is its simple type. For instance Int has kind * which means it's a base type and can be instantiated by values. By some loose definition of higher-kinded type (and I'm not sure where F# draws the line, so let's just include it) polymorphic containers are a great example of a higher-kinded type.

data List a = Cons a (List a) | Nil

The type constructor List has kind * -> * which means that it must be passed a concrete type in order to result in a concrete type: List Int can have inhabitants like [1,2,3] but List itself cannot.

I'm going to assume that the benefits of polymorphic containers are obvious, but more useful kind * -> * types exist than just the containers. For instance, the relations

data Rel a = Rel (a -> a -> Bool)

or parsers

data Parser a = Parser (String -> [(a, String)])

both also have kind * -> *.


We can take this further in Haskell, however, by having types with even higher-order kinds. For instance we could look for a type with kind (* -> *) -> *. A simple example of this might be Shape which tries to fill a container of kind * -> *.

data Shape f = Shape (f ())

Shape [(), (), ()] :: Shape []

This is useful for characterizing Traversables in Haskell, for instance, as they can always be divided into their shape and contents.

split :: Traversable t => t a -> (Shape t, [a])

As another example, let's consider a tree that's parameterized on the kind of branch it has. For instance, a normal tree might be

data Tree a = Branch (Tree a) a (Tree a) | Leaf

But we can see that the branch type contains a Pair of Tree as and so we can extract that piece out of the type parametrically

data TreeG f a = Branch a (f (TreeG f a)) | Leaf

data Pair a = Pair a a
type Tree a = TreeG Pair a

This TreeG type constructor has kind (* -> *) -> * -> *. We can use it to make interesting other variations like a RoseTree

type RoseTree a = TreeG [] a

rose :: RoseTree Int
rose = Branch 3 [Branch 2 [Leaf, Leaf], Leaf, Branch 4 [Branch 4 []]]

Or pathological ones like a MaybeTree

data Empty a = Empty
type MaybeTree a = TreeG Empty a

nothing :: MaybeTree a
nothing = Leaf

just :: a -> MaybeTree a
just a = Branch a Empty

Or a TreeTree

type TreeTree a = TreeG Tree a

treetree :: TreeTree Int
treetree = Branch 3 (Branch Leaf (Pair Leaf Leaf))

Another place this shows up is in "algebras of functors". If we drop a few layers of abstractness this might be better considered as a fold, such as sum :: [Int] -> Int. Algebras are parameterized over the functor and the carrier. The functor has kind * -> * and the carrier kind * so altogether

data Alg f a = Alg (f a -> a)

has kind (* -> *) -> * -> *. Alg useful because of its relation to datatypes and recursion schemes built atop them.

-- | The "single-layer of an expression" functor has kind `(* -> *)`
data ExpF x = Lit Int
            | Add x x
            | Sub x x
            | Mult x x

-- | The fixed point of a functor has kind `(* -> *) -> *`
data Fix f = Fix (f (Fix f))

type Exp = Fix ExpF

exp :: Exp
exp = Fix (Add (Fix (Lit 3)) (Fix (Lit 4))) -- 3 + 4

fold :: Functor f => Alg f a -> Fix f -> a
fold (Alg phi) (Fix f) = phi (fmap (fold (Alg phi)) f)

Finally, though they're theoretically possible, I've never see an even higher-kinded type constructor. We sometimes see functions of that type such as mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b, but I think you'll have to dig into type prolog or dependently typed literature to see that level of complexity in types.

18
  • 3
    I'll type-check and edit the code in a few minutes, I'm on my phone right now. Commented Jan 16, 2014 at 19:37
  • 13
    @J.Abrahamson +1 for a good answer and having the patience to type that on your phone O_o Commented Jan 16, 2014 at 19:40
  • 3
    @lobsterism A TreeTree is just pathological, but more practically it means that you've got two different types of trees interwoven between one another—pushing that idea a little further can get you some very powerful type-safe notions such as statically-safe red/black trees and the neat statically balanced FingerTree type. Commented Jan 16, 2014 at 19:55
  • 3
    @JonHarrop A standard real-world example is abstracting over monads, e.g. with mtl-style effect stacks. You may not agree that this is real world valuable, though. I think it's generally clear that languages can successfully exist without HKTs, so any example will be providing some kind of abstraction which is more sophisticated than other languages. Commented Sep 26, 2015 at 13:02
  • 2
    You can have, e.g. subsets of authorized effects in various monads and abstract over any monads meeting that specification. For instance, monads instantiating "teletype" which enables character level reading and writing might include both IO and a pipe abstraction. You could abstract over various asynchronous implementations as another example. Without HKTs you limit any type composed from that generic piece. Commented Sep 26, 2015 at 21:04
68

Consider the Functor type class in Haskell, where f is a higher-kinded type variable:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

What this type signature says is that fmap changes the type parameter of an f from a to b, but leaves f as it was. So if you use fmap over a list you get a list, if you use it over a parser you get a parser, and so on. And these are static, compile-time guarantees.

I don't know F#, but let's consider what happens if we try to express the Functor abstraction in a language like Java or C#, with inheritance and generics, but no higher-kinded generics. First try:

interface Functor<A> {
    Functor<B> map(Function<A, B> f);
}

The problem with this first try is that an implementation of the interface is allowed to return any class that implements Functor. Somebody could write a FunnyList<A> implements Functor<A> whose map method returns a different kind of collection, or even something else that's not a collection at all but is still a Functor. Also, when you use the map method you can't invoke any subtype-specific methods on the result unless you downcast it to the type that you're actually expecting. So we have two problems:

  1. The type system doesn't allow us to express the invariant that the map method always returns the same Functor subclass as the receiver.
  2. Therefore, there's no statically type-safe manner to invoke a non-Functor method on the result of map.

There are other, more complicated ways you can try, but none of them really works. For example, you could try augment the first try by defining subtypes of Functor that restrict the result type:

interface Collection<A> extends Functor<A> {
    Collection<B> map(Function<A, B> f);
}

interface List<A> extends Collection<A> {
    List<B> map(Function<A, B> f);
}

interface Set<A> extends Collection<A> {
    Set<B> map(Function<A, B> f);
}

interface Parser<A> extends Functor<A> {
    Parser<B> map(Function<A, B> f);
}

// …

This helps to forbid implementers of those narrower interfaces from returning the wrong type of Functor from the map method, but since there is no limit to how many Functor implementations you can have, there is no limit to how many narrower interfaces you'll need.

(EDIT: And note that this only works because Functor<B> appears as the result type, and so the child interfaces can narrow it. So AFAIK we can't narrow both uses of Monad<B> in the following interface:

interface Monad<A> {
    <B> Monad<B> flatMap(Function<? super A, ? extends Monad<? extends B>> f);
}

In Haskell, with higher-rank type variables, this is (>>=) :: Monad m => m a -> (a -> m b) -> m b.)

Yet another try is to use recursive generics to try and have the interface restrict the result type of the subtype to the subtype itself. Toy example:

/**
 * A semigroup is a type with a binary associative operation.  Law:
 *
 * > x.append(y).append(z) = x.append(y.append(z))
 */
interface Semigroup<T extends Semigroup<T>> {
    T append(T arg);
}

class Foo implements Semigroup<Foo> {
    // Since this implements Semigroup<Foo>, now this method must accept 
    // a Foo argument and return a Foo result. 
    Foo append(Foo arg);
}

class Bar implements Semigroup<Bar> {
    // Any of these is a compilation error:

    Semigroup<Bar> append(Semigroup<Bar> arg);

    Semigroup<Foo> append(Bar arg);

    Semigroup append(Bar arg);

    Foo append(Bar arg);

}

But this sort of technique (which is rather arcane to your run-of-the-mill OOP developer, heck to your run-of-the-mill functional developer as well) still can't express the desired Functor constraint either:

interface Functor<FA extends Functor<FA, A>, A> {
    <FB extends Functor<FB, B>, B> FB map(Function<A, B> f);
}

The problem here is this doesn't restrict FB to have the same F as FA—so that when you declare a type List<A> implements Functor<List<A>, A>, the map method can still return a NotAList<B> implements Functor<NotAList<B>, B>.

Final try, in Java, using raw types (unparametrized containers):

interface FunctorStrategy<F> {
    F map(Function f, F arg);
} 

Here F will get instantiated to unparametrized types like just List or Map. This guarantees that a FunctorStrategy<List> can only return a List—but you've abandoned the use of type variables to track the element types of the lists.

The heart of the problem here is that languages like Java and C# don't allow type parameters to have parameters. In Java, if T is a type variable, you can write T and List<T>, but not T<String>. Higher-kinded types remove this restriction, so that you could have something like this (not fully thought out):

interface Functor<F, A> {
    <B> F<B> map(Function<A, B> f);
}

class List<A> implements Functor<List, A> {

    // Since F := List, F<B> := List<B>
    <B> List<B> map(Function<A, B> f) {
        // ...
    }

}

And addressing this bit in particular:

(I think) I get that instead of myList |> List.map f or myList |> Seq.map f |> Seq.toList higher kinded types allow you to simply write myList |> map f and it'll return a List. That's great (assuming it's correct), but seems kind of petty? (And couldn't it be done simply by allowing function overloading?) I usually convert to Seq anyway and then I can convert to whatever I want afterwards.

There are many languages that generalize the idea of the map function this way, by modeling it as if, at heart, mapping is about sequences. This remark of yours is in that spirit: if you have a type that supports conversion to and from Seq, you get the map operation "for free" by reusing Seq.map.

In Haskell, however, the Functor class is more general than that; it isn't tied to the notion of sequences. You can implement fmap for types that have no good mapping to sequences, like IO actions, parser combinators, functions, etc.:

instance Functor IO where
    fmap f action =
        do x <- action
           return (f x)

 -- This declaration is just to make things easier to read for non-Haskellers 
newtype Function a b = Function (a -> b)

instance Functor (Function a) where
    fmap f (Function g) = Function (f . g)  -- `.` is function composition

The concept of "mapping" really isn't tied to sequences. It's best to understand the functor laws:

(1) fmap id xs == xs
(2) fmap f (fmap g xs) = fmap (f . g) xs

Very informally:

  1. The first law says that mapping with an identity/noop function is the same as doing nothing.
  2. The second law says that any result that you can produce by mapping twice, you can also produce by mapping once.

This is why you want fmap to preserve the type—because as soon as you get map operations that produce a different result type, it becomes much, much harder to make guarantees like this.

4
  • So I'm interested in your last bit, why is it useful to have an fmap on Function a when it already has a . operation? I understand why . makes sense to be the definition of the fmap op, but I just don't get where you'd ever need to use fmap instead of .. Maybe if you could give an example where that would be useful, it'd help me understand.
    – lobsterism
    Commented Jan 18, 2014 at 3:32
  • 1
    Ah, got it: you can make a fn double of a functor, where double [1, 2, 3] gives [2, 4, 6] and double sin gives a fn that is double the sin. I can see where if you start thinking in that mindset, when you run a map on an array you expect an array back, not just a seq, because, well, we're working on arrays here.
    – lobsterism
    Commented Jan 18, 2014 at 4:57
  • @lobsterism: There are algorithms/techniques that rely on being able to abstract out a Functor and let the client of the library pick it out. J. Abrahamson's answer provides one example: recursive folds can be generalized by using functors. Another example is free monads; you can think of these as a kind of generic interpreter implementation library, where the client supplies the "instruction set" as an arbitrary Functor. Commented Jan 18, 2014 at 5:38
  • 3
    A technically sound answer but it leaves me wondering why anyone would ever want this in practice. I've not found myself reaching for Haskell's Functor or a SemiGroup. Where do real programs most use this language feature?
    – J D
    Commented Sep 26, 2015 at 11:50
32

I don't want to repeat information in some excellent answers already here, but there's a key point I'd like to add.

You usually don't need higher-kinded types to implement any one particular monad, or functor (or applicative functor, or arrow, or ...). But doing so is mostly missing the point.

In general I've found that when people don't see the usefulness of functors/monads/whatevers, it's often because they're thinking of these things one at a time. Functor/monad/etc operations really add nothing to any one instance (instead of calling bind, fmap, etc I could just call whatever operations I used to implement bind, fmap, etc). What you really want these abstractions for is so you can have code that works generically with any functor/monad/etc.

In a context where such generic code is widely used, this means any time you write a new monad instance your type immediately gains access to a large number of useful operations that have already been written for you. That's the point of seeing monads (and functors, and ...) everywhere; not so that I can use bind rather than concat and map to implement myFunkyListOperation (which gains me nothing in itself), but rather so that when I come to need myFunkyParserOperation and myFunkyIOOperation I can re-use the code I originally saw in terms of lists because it's actually monad-generic.

But to abstract across a parameterised type like a monad with type safety, you need higher-kinded types (as well explained in other answers here).

5
  • 10
    This is closer to being a useful answer than any of the other answers I've read so far but I'd still like to see a single practical application where higher kinds are useful.
    – J D
    Commented Sep 26, 2015 at 12:00
  • "What you really want these abstractions for is so you can have code that works generically with any functor/monad". F# got monads in the form of computation expressions 13 years ago, originally sporting seq and async monads. Today F# enjoys a 3rd monad, query. With so few monads that have so little in common why would you want to abstract over them?
    – J D
    Commented Mar 13, 2020 at 20:47
  • 2
    @JonHarrop You're clearly aware that other people have written code using huge numbers of monads (and functors, arrows, etc; HKTs are not just about monads) in languages that do support HKTs, and find uses for abstracting over them. And clearly you don't think any of that code has any practical use, and are curious why other people would bother to write it. What sort of insight are you hoping to gain by coming back to start a debate on a 6 year old post that you've already commented on 5 years ago?
    – Ben
    Commented Mar 13, 2020 at 21:39
  • "hoping to gain by coming back to start a debate on a 6 year old post". Retrospective. With the benefit of hindsight we now know that F#'s abstractions over monads remain largely unused. Therefore the ability to abstract over 3 largely different things is uncompelling.
    – J D
    Commented Mar 14, 2020 at 17:59
  • 3
    @JonHarrop The point of my answer is that individual monads (or functors, or etc) are not really any more useful than similar functionality expressed without a nomadic interface, but that unifying lots of disparate things is. I'll defer to your expertise on F#, but if you're saying it only has 3 individual monads (rather than implementing a monadic interface to all of the concepts that could have one, like failure, statefulness, parsing, etc), then yes, it's unsurprising that you wouldn't get much benefit from unifying those 3 things.
    – Ben
    Commented Mar 14, 2020 at 21:46
15

For a more .NET-specific perspective, I wrote a blog post about this a while back. The crux of it is, with higher-kinded types, you could potentially reuse the same LINQ blocks between IEnumerables and IObservables, but without higher-kinded types this is impossible.

The closest you could get (I figured out after posting the blog) is to make your own IEnumerable<T> and IObservable<T> and extended them both from an IMonad<T>. This would allow you to reuse your LINQ blocks if they're denoted IMonad<T>, but then it's no longer typesafe because it allows you to mix-and-match IObservables and IEnumerables within the same block, which while it may sound intriguing to enable this, you'd basically just get some undefined behavior.

I wrote a later post on how Haskell makes this easy. (A no-op, really--restricting a block to a certain kind of monad requires code; enabling reuse is the default).

4
  • 2
    I'll give you a +1 for being the only answer that mentions something practical but I don't think I've ever used IObservables in production code.
    – J D
    Commented Sep 26, 2015 at 12:02
  • 8
    @JonHarrop This seems untrue. In F# all events are IObservable, and you use events in the WinForms chapter of your own book.
    – Dax Fohl
    Commented Oct 19, 2016 at 17:50
  • Reuse between IQueryable and IEnumerable would be possible too I suppose
    – KolA
    Commented Jul 26, 2019 at 8:48
  • Four years later and I've finished looking: we stripped Rx out of production.
    – J D
    Commented Mar 13, 2020 at 20:49
13

The most-used example of higher-kinded type polymorphism in Haskell is the Monad interface. Functor and Applicative are higher-kinded in the same way, so I'll show Functor in order to show something concise.

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Now, examine that definition, looking at how the type variable f is used. You'll see that f can't mean a type that has value. You can identify values in that type signature because they're arguments to and results of a functions. So the type variables a and b are types that can have values. So are the type expressions f a and f b. But not f itself. f is an example of a higher-kinded type variable. Given that * is the kind of types that can have values, f must have the kind * -> *. That is, it takes a type that can have values, because we know from previous examination that a and b must have values. And we also know that f a and f b must have values, so it returns a type that must have values.

This makes the f used in the definition of Functor a higher-kinded type variable.

The Applicative and Monad interfaces add more, but they're compatible. This means that they work on type variables with kind * -> * as well.

Working on higher-kinded types introduces an additional level of abstraction - you aren't restricted to just creating abstractions over basic types. You can also create abstractions over types that modify other types.

1
  • 4
    Another great technical explanation of what higher kinds are that leaves me wondering what they are useful for. Where have you leveraged this in real code?
    – J D
    Commented Sep 26, 2015 at 11:57
-1

Why might you care about Applicative? Because of traversals.

class (Functor t, Foldable t) => Traversable t where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f t

Once you've written a Traversable instance, or a Traversal for some type, you can use it for an arbitrary Applicative.

Why might you care about Monad? One reason is streaming systems like pipes, conduit, and streaming. These are entirely non-trivial systems for working with effectful streams. With the Monad class, we can reuse all that machinery for whatever we like, rather than having to rewrite it from scratch each time.

Why else might you care about Monad? Monad transformers. We can layer monad transformers however we like to express different ideas. The uniformity of Monad is what makes this all work.

What are some other interesting higher-kinded types? Let's say ... Coyoneda. Want to make repeated mapping fast? Use

data Coyoneda f a = forall x. Coyoneda (x -> a) (f x)

This works or any functor f passed to it. No higher-kinded types? You'll need a custom version of this for each functor. This is a pretty simple example, but there are much trickier ones you might not want to have to rewrite every time.

-4

Recently stated learning a bit about higher kinded types. Although it's an interesting idea, to be able to have a generic that needs another generic but apart from library developers, i do not see any practical use in any real app. I use scala in business app, i have also seen and studied the code of some nicely designed sgstems and libraries like kafka, akka and some financial apps. Nowhere I found any higher kinded type in use.

It seems like they are nice for academia or similar but the market doesn't need it or hasn't reached to a point where HKT has any practical uses or proves to be better than other existing techniques. To me it's something that you can use to impress others or write blog posts but nothing more than that. It's like multiverse or string theory. Looks nice on paper, gives you hours to speak about but nothing real (sorry if you don't have any interest in theoratical physiss). One prove is that all the answers above, they all brilliantly describe the mechanics fail to cite one true real case where we would need it despite being the fact it's been 6+ years since OP posted it.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.