Where are the monads, CPS and these functional buzzwords in Nix?

1

This is mostly a curiosity of mine.

I learned a bit of Haskell by reading Yet Another Haskell Tutorial.
I had a mind blowing moment with the concepts of Continuation Passing Style and Monads.
I am still trying to understand them, to be honest.

With this background I ask for each and every person interested in some interaction:

  • Have you ever seen something related to {continuation passing style, monads} written in the Nix language?
  • Do you believe these functional design patterns can be useful in Nixpkgs?
1 Like
2

Monads as an abstraction only make sense in a statically-typed language. It can make sense to use functions that happen to be monadic binds for a specific type in a dynamically-typed language like Nix (builtins.concatMap is bind for lists, of course/for example), but IMO the concept of abstracting over multiple monads with a uniform API or syntax is unlikely to be helpful in this version of the Nix language.

I haven’t seen a need for CPS in any Nix code I’ve worked with, but someone conceivably could have!

2 Likes
3

I don’t necessarily think monads and continuation passing style wouldn’t be useful in Nix; I think the language just isn’t really expressive enough for them. The ability to have generic functions that work with arbitrary effects, like State, Maybe, and Either is something I’ve often wanted in non-Haskell languages, including Nix. My favorite example of these sorts of things is the Traversable class

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

instance Traversable [] where
  traverse _ [] = pure []
  traverse f (x:xs) = liftA2 (:) (f x) (traverse f xs)

Which lets you iterate over arbitrary collections using arbitrary effects. Now, in Nix, we’re likely to only really need lists and attrsets, so I don’t really mind needing to use specific traverseList and traverseAttrs functions or something; but the important part is being able to create arbitrary monads / applicatives that work with those. And Nix just doesn’t really have the expressiveness to do these things cleanly. You can use a bunch of unwieldy workarounds to get it done, but you end up with stuff like explicit dictionary passing and church encoding.

rec {
  # A church encoded `Either a b` is a function of type
  # `(a -> r) -> (b -> r) -> r`,
  # which simply calls the left or right higher order
  # function argument depending on if it's a `Left` or a `Right`
  mkLeft = x: left: right: left x;
  mkRight = x: left: right: right x;

  # An `Applicative` instance can be represented
  # with an explicit dictionary.
  eitherApplicative = {
    pure = mkRight;
    liftA2 = f: x: y: left: right:
      x left (xRight: y left (yRight: right (f xRight yRight)));
  };

  traverseList = applicativeDict: f: xs:
    builtins.foldl'
      (acc: x: applicativeDict.liftA2 (ys: y: ys ++ [y]) acc (f x))
      (applicativeDict.pure [])
      xs;

  fmap = applicativeDict: f: x:
    applicativeDict.liftA2
      (_: y: f y)
      (applicativeDict.pure null)
      x;

  # This example will return `Left x`, where `x` is the first even number
  # Or it will return `Right (sum xs)` if there are no evens.
  example = xs: let
    isEven = x: builtins.bitAnd 1 x == 0;
    sum = builtins.foldl' (acc: x: acc + x) 0;
    odds = traverseList
      eitherApplicative
      (x: if isEven x then mkLeft x else mkRight x)
      xs;
  in fmap eitherApplicative sum odds;
}

nix-repl> example [1 3 5] (e: "There's an even ${toString e}") (s: "The sum is ${toString s}")
"The sum is 9"

nix-repl> example [1 2 3 5] (e: "There's an even ${toString e}") (s: "The sum is ${toString s}")
"There's an even 2"
1 Like