The hand-painted look is a compelling game art style. It adds a whimsically fantastical feel that photorealism lacks. However, actually achieving the look can be quite tedious — sometimes requiring hours for a single texture.

Below is a way I’ve come up with for approximating the hand-painted look that can stand on its own — or if needed — be the basis for a hand-painted texture without having to start from a blank canvas. This process is especially helpful for those pressed for time, say during a game jam.

The nice thing about this technique is that you can dial in how much or how little stylization you want.

Using it on a variety of textures, I haven’t found a case where it completely fails to give that hand painted look.

Finding A Photo Texture

The process starts with a real photo. Somewhere in the photo you choose is a hand-painted texture lurking in the details. Your goal is to remove the right details to reveal the hand-painted texture hidden underneath. When you’re actually painting the texture, you’re trying to build up the details while here, you are trying to tear them down.

I tend to use Pixabay to find my photo textures. Most of the images are free for commercial use and require no attribution which is always nice when developing your own game.

⚠️ Make sure to find one evenly lit and head on when browsing through the photos.

Preparing The Photo

Depending on your needs, you might be able to skip the photo prep. However, in the interest of documenting the most involved case, I’ll demonstrate the technique by creating a seamless/tileable, square, power-of-two texture which tends to be the most versatile.

The photo I’ve chosen is a bit bowed so you’ll want to straighten it out before you do anything. You can do this with the warp tool.

Next, crop the photo where the width and height are the same size and a power of two (256x256, 512x512, 1024x1024, etc.). To help make the texture seamless, try to crop it in such a way that the left and right and the top and bottom sort of mirror each other.

If you don’t already have it, make sure to install G’MIC. I use it as a Krita plugin but you can also use it online. With G’MIC open, find the Make Seamless [Diffusion] filter. This will help remove the seams without having to use the heal/patch or clone tool.

The seams should be more or less gone now. However, the Make Seamless filter tends to introduce uneven lighting so you’ll have to play around with the Equalize Light setting. If the Equalize Light setting doesn’t work, you can try the Normalize Brightness filter after using Make Seamless.

Splitting The Details

With the prep done, we can now move on to the stylization.

With G’MIC open, go to the Split Details [Wavelets] filter. Set the Number of Scales to four and click apply. The first split is the small details, the second is the medium details, the third is the large details, and the fourth is the residual or what’s left over. You can try more or less splits but I’ve found four to be the ideal number.

After splitting the details, rename the layers 1 through 4 so you can easily reference them later. Layer 1, 2, and 3 should be set to Grain Merge. After setting the blend mode, you’ll notice that you have the original image back.

Adding The Brush Strokes

It wouldn’t be hand painted without brush strokes. After splitting the details, run layer 4 through the Brushify filter found in G’MIC.

Under the Brush Parameters, set the Shape to Rectangle, the Number of Sizes to 2, the Maximal Size to 45, the Light Type to None, the Light Strength to 0, and the Opacity to 1. These are the ideals settings I’ve found but feel free to experiment. Depending on how “painted” you want it to look, play around with the Number of Sizes.

💡 The goal here is to see the brush strokes so having it rough around the edges is fine. You want it to look like the colors and shading have all been roughed in but haven’t been smoothed out yet.

Smoothing Out The Details

Recall that our goal is to remove just enough detail to reveal the hidden hand painted texture underneath. Layers 1 through 3 hold the small, medium, and large details respectively. For layers 1, 2, and 3, you’ll want to smooth out the details until they each have that chunky, painterly look.

With G’MIC open, navigate to the Smooth [Thin Brush] filter. I’ve found this smoothing filter to work the best for this step but feel free to try the others. The goal here is to retain the important edges or contours while blurring out the rest.

Here you see me smoothing out layer 1. I take out most of the detail, retaining just a slight hint of the surface detail found on the stones and moss.

Seamless

After using Brushify on layer 4 and Smooth [Thin Brush] on layers 1 through 3, we have seams again. To remedy this, apply the Make Seamless filter to layers 3 and 4. You can try it on layers 2 and 1 but I’ve found it does more harm than good.

For example, here you see Make Seamless applied to layer 2. Notice the uneven lighting where it looks pinched in certain spots.

To remove the seams in layers 1 and 2, use the clone tool to lightly smooth away the obvious edges.

⚠️ Be careful not to introduce phantom details by cloning some detail that wasn’t there before.

Creating The Normal Map

So far we’ve been working on the diffuse map. The diffuse map defines the color of your game model as if it was fully lit. However, we’d like to incorporate the surface details we see in the diffuse map into the shading or lighting performed by the game engine. To do that, we’ll need to create a normal map.

💡 To learn more about the technical side of normal mapping, be sure to check out 3D Game Shaders For Beginners.

Before creating the normal map, take a look at layers 1 through 3 and decide on how much detail you would like to incorporate. Typically, layer 3 is enough but sometimes I add in layer 2 as well.

After you have decided how much detail to include, copy the layers and merge them together. Move this layer up above 1 and set its blend mode to normal. Now take this layer and desaturate it using the average setting.

At this point, you’ll want to look up how to create a normal map using your preferred program. For Krita, it has a built-in filter called Height to Normal Map. Select Filter ▶️ Edge Detection ▶️ Height to Normal Map and choose from either Prewitt, Sobel, or Simple. I tend to use Sobel or Simple the most. If the details are extra light then I’ll choose Prewitt. After clicking OK, rename this layer normal and hide every layer.

Creating The Cavity Map

From the normal map we’ll create the cavity map. The cavity map allows us to highlight the sharp ridges and shadow the narrow crevices found in the texture.

Select the normal map and then navigate to Image ▶️ Separate Image. This will separate the normal map into its blue, red, and green channels.

Select the blue layer and set it to multiply. Select the green layer and set it to overlay. With the green layer still selected, navigate to Filter ▶️ Edge Detection ▶️ Edge Detection. Like the normal map, select from either Prewitt, Sobel, or Simple. For the green layer, set the Output to Bottom Edge and click OK. Now do the same for the red layer but this time set the Output to Right Edge.

After the edge detection, merge the green layer into the red layer and then merge the blue layer into the red layer. Rename this layer cavity and place it above layer 1. Set the blend mode for cavity to overlay.

The cavity map most likely has seams so you’ll want to try using Make Seamless and if that doesn’t work, clean up the edges using the clone tool like you did before.

At this point the cavity map is finished but you may want to adjust its contrast in case the highlights are too harsh and/or smooth it out with the Thin Brush filter if it’s too noisy.

Creating The Occlusion Map

The last map we’ll create is the ambient occlusion map. This map allows us to shadow the larger recessed regions in our texture that receive less light. Your game engine can also use it when it applies the ambient lighting.

The cavity map and ambient occlusion map tend to overlap but in general the ambient occlusion map shadows the larger occluded areas while the cavity map handles the smaller occluded areas. The cavity map also highlights the sharply raised areas.

Similar to the normal map, select, copy, and merge the details layers you would like to include in the ambient occlusion map. Once merge, desaturate this new layer using the Min option.

With G’MIC open, navigate to the Basic Adjustments filter. Play with the brightness and contrast until you have the desired result. You'll want the raised areas to be white and the recessed areas to be a soft grey. When you have the look you want, press Apply and set this layer’s blend mode to multiply.

Color Correction

The stylization process is now complete but before you export you may want to perform some color correction on layer 4.

I enjoy using the G’MIC Basic Adjustments filter for this step.

Another filter to try is G’MIC’s Auto Balance. This may not always work but when it does, it can definitely save some time when you’re trying to get the colors just right.

Just before I export, I like to toggle on and off the original. This allows me to see how much of a change I made, whether or not I got all the details I wanted, and if I overdid it with the color correction.

Putting It All Together

You now have your diffuse, normal, ambient occlusion, and cavity map.

With these maps, you can now move over to your modeling program (I use Blender) and assemble your material.

In this scene, I used the same process described up above to create the wood, roof, grass, water, rope, bark, butterfly, rock, leaves, shrub, and metal texture. I’ve uploaded the model to Sketchfab so you can take a closer look.

Using only a couple of free tools (Krita and G’MIC), I’ve put together a fairly easy process for creating diffuse, normal, cavity, and occlusion maps that approximate the hand-painted game art style.

Hopefully this will save you some time when developing your own games. If you happen to use the process, be sure to share your creation in the comments below. 👍

When I last wrote about binding PureScript to C++, I demonstrated animating the PureScript logo with SFML. Since then, PureScript Native (PSN) has superseded Pure11 and the details for using PSN have changed.

To make this concrete, I’ll go over what it took to create Lambda Lantern — a 3D game about functional programming patterns. Originally Lambda Lantern started off as a GitHub Game Off submission. Since you only have 30 or so days to finish, some shortcuts had to be made. I plan to address the shortcuts and really flesh out the game using it as a vehicle to drive the C++ binding and the ecosystem around it.

💡 If you’re not looking to make a game but would still like to bind PureScript to C++ code or maybe you’re looking for an alternative to binding Haskell to C++ — no worries — I’ve tried to keep this guide as general as possible.

Setting up the Project

Git clone PSN and build it with stack like you would any other Haskell Stack project.

git clone https://github.com/andyarvanitis/purescript-native
cd purescript-native
stack install
cd

Once it finishes, you’ll end up with the PureScript to C++ compiler called pscpp. If you stack installed, it should be in your local bin directory. In any case, make sure your path environment variable has the path to pscpp.

export PATH="${PATH}:${HOME}/.local/bin"

Next you’ll need Node.js and NPM. I like to manage Node with NVM

git clone https://github.com/lettier/lambda-lantern.git
cd lambda-lantern/
nvm install `cat .nvmrc` && nvm use

but feel free to use a method you enjoy. Install purescript and psc-package like so.

npm install -g purescript psc-package-bin-simple

PSN can generate a convenient Makefile that manages the build process. If the Makefile is not already present, go ahead and generate that now.

pscpp --makefile

Lambda Lantern already has a package set for psc-package. I couldn’t use the more common one since I needed to include Andy Arvanitis’ fork of the prelude. The fork doesn’t rely on the unsafe, implicit-type equality comparisons. Later on, these were removed in version 4.1.1 of the prelude. This should allow me to use the original ecosystem. Anyway, you can always develop your own package set with psc-package init and pointing the psc-package.json file to your local or remote repository containing your packages.json file.

Once you have your psc-package.json file ready, install the PureScript dependencies with the following command.

psc-package install

If you look under .psc-package/ you’ll see all of the PureScript code for your package set but you’re still missing the C++ FFI (foreign function interface).

Create a ffi/ directory in the main directory of your project. The Makefile that you generated earlier is configured to look there. You can of course change it but be sure to update the Makefile.

Clone the contents of purescript-native-ffi into the ffi/ directory.

⚠️ For Lambda Lantern, when cloning the FFI repository, be careful not to overwrite any existing files as I had to make some modifications and additions.

git clone \
  https://github.com/andyarvanitis/purescript-native-ffi.git
cp -nr purescript-native-ffi/. lambda-lantern/ffi/

Your project directory should look something like this.

/
  .psc-package/
  ffi/
  node_modules/
  src/
    Main.purs
  Makefile
  psc-package.json

At this point you’ll want to install the game engine or C++ code you’ll be binding to. For Lambda Lantern, you’ll need to install Panda3D. Panda3D has installers for Linux, macOS, and Windows.

Picking the Game Engine

After reviewing quite a few C++ based game engines, I decided on Panda3D as it had the most straightforward API to bind to. Panda3D comes with most of the functionality you see elsewhere like shaders, particle effects, physics, multiple render targets, 3D audio, etc. Still, if you prefer another engine then feel free to use that one instead. The basic idea to this guide is still applicable.

A common pattern I noticed in a lot of the engines I reviewed was the need to inherit from some application class. The game engine controls main and calls your filled out application class Hollywood principle style. Having the engine control main would make for an awkward C++ and PureScript sandwich — starting and ending in C++ with the PureScript game logic in the middle. You could, I’m sure, deconstruct the application class and replicate what the engine is doing in main but with Panda3D available, I didn’t see the need.

The documentation for Panda3D is extensive but sometimes I had to dive into the code to find this or that class that didn’t show up in the C++ reference. The forums are also a great resource with over a decade of posts to search through. Sometimes you’ll come across outdated solutions so I recommend sorting by recent.

Creating the C++ FFI Exports

Here is a bare-bones PSN C++ FFI file.

#include "purescript.h"

FOREIGN_BEGIN(SomeModuleName)
FOREIGN_END

Between the foreign begin and end is where you define the exports that are called from the PureScript side.

exports["id"] = [](const boxed& param_) -> boxed {
  return param_;
};

To shuttle around parameters and return values, PSN uses the class boxed. This boxed class builds off of shared_ptr.

To work with a boxed value, you’ll have to unbox it, providing its type.

auto param = unbox<type>(param_);

⚠️ If you don’t know the type then you’re stuck. This is the issue with the implicit-type equality comparisons since the boxed values have their types erased.

💡 All exports have to accept boxed values and return boxed values. Some types like string, char, double, int, long, etc. can be returned directly. The compiler will construct a boxed value for you since the boxed class comes with a few convenient constructors.

exports["echo"] = [](const boxed& s_) -> boxed {
  const auto s = unbox<string>(s_);
  return s;
}; 

For other types, you’ll have to call the box procedure to box up your type.

exports["someFunction"] = [](const boxed& param_) -> boxed {
  auto param = unbox<Type>(param_);
  // ...
  return box<Type>(param);
};

You’ll need to curry your functions or in other words, return a new lambda function for each parameter. If your function returns an Effect, you’ll need an additional lambda function that takes no parameters.

In PureScript:

foreign import add1  :: Number -> Number

foreign import add1' :: Number -> Effect Number

In C++:

exports["add1"] = [](const boxed& n_) -> boxed {
  const auto n = unbox<double>(n_);
  return n + 1.0;
};
exports["add1'"] = [](const boxed& n_) -> boxed {
  const auto n = unbox<double>(n_);
  return [=]() -> boxed {
    return n + 1.0;
  };
};

Marking some import with Effect is up to you but generally if the function alters anything outside of its scope or returns different output for the same input, it should use Effect.

For those not familar with the syntax up above, PSN exports use C++ lambda functions.

[ ] // means don't capture any external variables.
[=] // means capture external variables by value.
[&] // means capture external variables by reference.

By value means make a duplicate copy of it so any edits to the copy won’t affect the original and by reference means make an alias such that any edits will affect the original. Ideally, you’ll want to use [=] instead of [&] so you don’t alter the input parameters.

Here’s some typical C++ lambda function patterns.

[&capture,=list](p,a,r,a,m,s) -> ReturnType { body; }
[&capture,=list](p,a,r,a,m,s)               { body; }
[&capture,=list]                            { body; }

I believe the best practice is to unbox your parameters as you receive them and use [=] for each returned lambda function like this.

[](const boxed& param_) -> boxed {
  const auto param = unbox<type>(param_);

  return [=](const boxed& param1_) -> boxed {
    const auto param1 = unbox<type>(param1_);

    return [=](const boxed& param2_) -> boxed {
      const auto param2 = unbox<type>(param2_);

        return ...
    };
  };
};

However, for certain exports, I had to unbox the parameters in the last lambda function only. For example, like this. Unboxing in the first lambda and then copying by reference like this caused a segfault. And I couldn’t unbox in the first lambda and then copy by value like this as the compiler would complain that I was trying to change a constant NodePath with set_scale. There was the option to use the mutable keyword like this but unboxing all the parameters in the last lambda function worked fine.

Another route would’ve been to dynamically allocate node paths —

// ...
return [&]() -> boxed {
  // ...
  const auto nodePathPtr = 
    std::make_shared<NodePath>(
      nodePath.find(query)
    );
  return nodePathPtr;
};
// ...

returning and accepting pointers to them — but this would’ve added unnecessary overhead. Still, with pointers, you can keep them constant, unbox them as soon as you receive them, and copy them by value using [=].

Generally, I stayed close to the Panda3D API. Ideally you want your exports to be very small and basic — putting any extra logic on the PureScript side for added protection. However, in some cases, I deviated when the procedures were routine and repetitive.

Binding to some of the Panda3D API wasn’t the only FFI needed. There was also the need to create FFI exports for commonplace functionality like now, JS centric functions like setInterval, requestAnimationFrame, etc., and looking up system environment variables — something completely foreign to JavaScript (in the browser at least).

💡 Most of the PureScript ecosystem assumes a JavaScript back end which is understandable. Hopefully though, PSN usage grows — increasing with it the C++ FFI coverage. Being able to easily target both the web and native platforms with just PureScript is definitely ideal.

One particular FFI call was for the browser window, which wasn’t applicable, so I filled it out with a no-op.

exports["window"] = []() -> boxed { return boxed(); };

⚠️ Note that the PSN run time will throw an error if it can’t find the FFI export for some FFI call. If this happens, you’ll see something like the following.

terminate called after throwing an instance of
'std::runtime_error'

what():  dictionary key "setInterval" not found

Obviously it would be great if this was caught at compile time but that may not be feasible.

I knew I wanted to use functional reactive programming (FRP) so I needed purescript-behaviors and purescript-event. The former uses requestAnimationFrame while the later uses clearInterval and setInterval.

Counting down the days to the end of the game jam, I decided to go with a simple multi-threaded model to emulate these JS centric functions in C++. Dealing with multiple threads versus JavaScript’s singled threaded nature, there were some subtle and not so subtle differences to my FRP events.

In JavaScript this

setInterval
  ( function () { while (true) { console.log(1); } }
  , 1000
  );
setInterval
  ( function () { while (true) { console.log(2); } }
  , 1000
  );

would only ever print 1 over and over, never giving the second interval a chance. But in C++ (using my FFI) something like this

setInterval
  ( [] { while (true) { std::cout << 1 << "\n"; } }
  , 1000
  );
setInterval
  ( [] { while (true) { std::cout << 2 << "\n"; } }
  , 1000
  );

would print 1 and 2 over and over again concurrently.

I plan to return to the multi-threaded model and convert it to a single-threaded, non-preemptive priority queue scheduling model to be more like its JavaScript counterpart.

Creating the PureScript FFI Imports

The PureScript side of the FFI fence wasn’t all that eventful. Having more time, I would’ve created typeclasses to emulate the class hierarchies found in Panda3D. Now that the game jam is over, I can go through and tidy up the interfaces abstracting out the commonalities.

Creating the PureScript FFI calls for C++ is the same as it is for JavaScript.

Here’s an example FFI call to create an ambient light.

foreign import data PandaNode :: Type

-- ...

foreign import createAmbientLight
  :: String
  -> Number
  -> Number
  -> Number
  -> Effect PandaNode

This import will call its C++ FFI export counterpart.

Looking at the pscpp generated C++, you can see how this is eventually hooked together.

auto createAmbientLight() -> const boxed& {
  static const boxed _ =
    foreign().at("createAmbientLight");
  return _;
};

// ...

boxed v27 =
  Panda3d::createAmbientLight
    ()
    ("ambientLight")
    (0.125)
    (0.122)
    (0.184)
    ();

Building the Project

💡 PSN uses the purs compiler (v0.12.0) so there isn’t any difference — PureScript wise — between the C++ and JavaScript targets.

Here’s the general outline to the build process.

• Compile the PureScript code by calling purs and outputting something called “CoreFn” which is the AST (abstract syntax tree) representation.
• Compile the CoreFn by calling pscpp and outputting C++.
• Compile and link the C++ by calling something like g++ and outputting the final executable.

Using the generated Makefile makes the build process super easy. It allows you to pass compiler and linker flags if needed. Here’s the make command I use to build Lambda Lantern

make \
  CXXFLAGS=" \
    -fmax-errors=1 \
    -I/usr/include/python \
    -I/usr/include/panda3d \
    -I/usr/include/freetype2" \
  LDFLAGS=" \
    -L/usr/lib/panda3d \
    -lp3framework \
    -lpanda \
    -lpandafx \
    -lpandaexpress \
    -lp3dtoolconfig \
    -lp3dtool \
    -lp3pystub \
    -lp3direct \
    -pthread \
    -lpthread"

Most of the flags are to include the Panda3D headers and link against the Panda3D libraries.

⚠️ /usr/include/python, /usr/include/panda3d, /usr/lib/panda3d, etc. may not be the exact paths for your system. You may also need additional flags not listed up above. For instance, on Ubuntu I have to include -I/usr/include/eigen3 .

After you build your project, the executable will be located in ./output/bin/.

Distributing the Project

PSN is cross platform between Linux, macOS, and Windows. For this section, I’ll cover what I did to distribute Lambda Lantern for Linux.

Having created snaps, flatpaks, AUR packages, and AppImages — I find AppImage to be the best experience for both distributor and user.

To start, you’ll want to find out what libraries your binary relies on.

objdump -p output/bin/main

Look for the “Dynamic Section” in the output.

Dynamic Section:
  NEEDED               libp3framework.so.1.10
  NEEDED               libpanda.so.1.10
  ...

⚠️ You may need additional libraries not listed. And even if you manged to include every single library, your AppImage may not run on older distributions depending on how up-to-date your build environment is (usually due to libc). I recommend using Ubuntu 14.04 or 16.04 as your build environment and then testing your AppImage on as many fresh installations as you can. If you missed any libraries, you’ll receive an error — telling you which library cannot be found — like the following.

error while loading shared libraries: libpanda.so.1.10: cannot open shared object file: No such file or directory

The nice thing about AppImage is you can include as many or as little libraries as you want. Ideally you’d include any library that isn’t typically found on the average system. This will give your AppImage the greatest chance of working out of the box.

Here’s the directory tree for the Lambda Lantern AppImage.

/
  etc/
    Confauto.prc
    Config.prc
  usr/
    lib/
      panda3d/
    share/
      applications/
        com.lettier.lambda-lantern.desktop
      icons/hicolor/256x256/
        com.lettier.lambda-lantern.png
      lambda-lantern/
        assets/
          eggs/
          fonts/
          music/
          sounds/
      licenses/
      metainfo/
        com.lettier.lambda-lantern.appdata.xml
  AppRun

The Config.prc and Confauto.prc files are required for Panda3D to run. In the AppRun file, I provided the path to the prc files and to Lambda Lantern’s assets directory. If you recall, I had to create a FFI export/import for looking up environment variables. At the beginning of the program, Lambda Lantern looks up an environment variable to find its assets.

export LAMBDA_LANTERN_ASSETS_PATH=\
  "${HERE}/usr/share/lambda-lantern/assets"
export PANDA_PRC_DIR="${HERE}/etc"

With all of the files in place and the AppRun file filled out, you create the AppImage like so.

appimagetool-x86_64.AppImage lambda-lantern.AppDir

The AppImage tool will perform some validation and then generate the AppImage if everything checks out.

If you’re using GitHub, you can upload the AppImage to a release for users to download. After downloading, users can mark the AppImage as executable and start playing! 🎉

Final Thoughts

Binding Haskell to C is fairly easy but not so with C++. This is unfortunate as some of the widely used libraries for game development are typically in C++. For awhile I tried various different methods for binding Haskell to C++ but it was never as straightforward as binding PureScript to C++ using PSN. If you’ve found a great way of binding Haskell to complex C++ projects do let me know. However, if you’ve been trying to bind Haskell to C++ — not finding any great options — strongly consider PSN.

Being able to bind PureScript to C++ opens up so many possibilities since there are so many great C++ based projects out there. From cutting edge game engines to robust machine learning libraries. Picking any one of them and gluing on top of it a PureScript interface gives you some distinct advantages.

Choosing Panda3D, I believe, is the right way forward. It doesn’t try to control the workflow — from concept to executable — making it perfect for me as I enjoy walking untravelled paths, seeing what’s possible like I did with the Gifcurry and Movie Monad projects. Originally, I wanted to use Godot but I needed it to be something I’d plug in instead of an environment that you augment from inside. If you know of a game that controls main and uses Godot with only C++, please let me know. Anyway, Panda3D is a real gem—dig around a bit you’ll find some great projects using it like the one below.

Hopefully others will use PSN more and more. I’m very excited to turn the concept behind Lambda Lantern into a full featured game but I’m even more excited about using it to get the word out and build up the ecosystem around PSN. In my opinion, being able to target both the web (JavaScript) and desktop (C++) with ease — using only PureScript— is a dream come true. 👍

Managing state. It’s the bane of programmers everywhere. The more stateful processes, subroutines, objects, components, widgets, doodads, etc. there are, the harder it is to keep your app from becoming a giant mud pit.

But fear not! You can use functional reactive programming (FRP) in your quest to manage state.

Imagine you have three entities called red, blue, and purple. Your job is to wire them all together such that red + blue = purple. Adjusting red and/or blue should automatically adjust purple.

Let’s try solving this imperatively and then we’ll switch to FRP.

First, create some objects capable of retaining and manipulating their own state.

Color = function() {
  this.color = 0;

  this.onChange = function() {};

  this.set = function(color) {
    this.color = color;
    this.onChange(this.color);};

  this.get = function() {return this.color;};

  this.setOnChange = function(fun) {
    this.onChange = fun;}}

red    = new Color();
blue   = new Color();
purple = new Color();

Next, set up the callbacks, wiring them together.

red.setOnChange(function(color){
  this.purple.set(color + this.blue.get());}.bind(this));

blue.setOnChange(function(color){
  this.purple.set(color + this.red.get());}.bind(this));

To see what’s going on, set up a logging callback for purple.

purple.setOnChange(function(color){
  console.log("Purple: " + color);});

And then test it out by changing the state of red and blue.

red.set(2);
blue.set(4);

Now let’s switch to FRP.

First, create the red and blue events.

red  <- create
blue <- create

From those, create some red and blue behaviors.

let red'  = step(0)(red.event)
let blue' = step(0)(blue.event)

And from those behaviors, create the purple behavior.

let plus b1 b2 = apply(map(+)(b1))(b2)

let purple = red' `plus` blue'

Like before, set up some logging.

let log' = log `compose` append("Purple: ") `compose` show
void(animate(purple)(log'))

And finally test it out by pushing some values for both red and blue.

red.push(2)
blue.push(4)

⚠️ If the FRP version seems completely alien 👽 — don’t worry. By the end you’ll understand it. 😃

Looking at the two, the FRP version is declarative. You declared or expressed the relationship that purple = red + blue. You gave the what, but not the how. You didn’t have to write any of the plumbing with callbacks. In both cases, whenever red or blue changes — purple changes. So we didn’t lose any functionality by using FRP.

What’s functional reactive programming?

Functional Reactive Programming, or FRP, is a general framework for programming hybrid systems in a high-level, declarative manner. The key ideas in FRP are its notions of behaviors and events. — Zhanyong Wan and Paul Hudak. 2000. Functional reactive programming from first principles.

It wasn’t always called “Functional Reactive Programming,” though. Initially it was called, “Functional Reactive Animation.”

Fran (Functional Reactive Animation) is a collection of data types and functions for composing richly interactive, multimedia animations. The key ideas in Fran are its notions of behaviors and events. — Conal Elliott and Paul Hudak. 1997. Functional reactive animation.

Over the years the term has been adopted and used to describe implementations that do not necessarily adhere to the precise mathematical specification or “denotational semantics” as laid out by Conal Elliott and Paul Hudak.

In any case, true (or what was originally) FRP deals with continuous (versus discrete) time, behaviors, and events. If something is called FRP but doesn’t model time as continuous, doesn’t use behaviors, and/or doesn’t use events then you might consider it, “Functional and Reactive Programming (F&RP).”

To make this concrete, I built a FRP demo called PureScript Pop 💥. Go ahead and have that open while you read along. When you get a chance, take a look at the source 📜. I made it very readable — even if you’ve never written PureScript before. 👍

What’s a behavior?

Behaviors are “time-varying values.” A behavior always has a value no matter what time it is and its value may change over time. Give me a point in time, a behavior, and I’ll always have a value for you. Behaviors are continuous variables with respect to time.

💡 The simplest behavior is just time itself. You give me a time and I give it right back to you.

Or you can get more complicated like is the mouse button down or up? No matter what the time, the mouse button is either down or up (assuming there’s no in-between transition).

let isMouseDown =
      step
        false
        (     (\ {value, buttons} ->
                value == 1 && member 0 buttons)
        `map` (withButtons
                mouse
                (
                      ((const 0) `map` up)
                `alt` ((const 1) `map` down))))

So as your application state moves through time, you can always count on behaviors having a value.

Behaviors get interesting when you combine them to create new behaviors — like combing red with blue to make purple.

unfold
  (\
    { isMouseDown'
    , isOverCoin'
    , isOverCoinSlot'
    }
    wasDragging
    ->
        not isOverCoinSlot'
    &&  (   (wasDragging  && isMouseDown')
        ||  (isMouseDown' && isOverCoin')
        ))
  (sample_
    (combine3Behaviors
      (Tuple
        (SProxy :: SProxy "isMouseDown'")
        isMouseDown)
      (Tuple
        (SProxy :: SProxy "isOverCoin'")
        isOverCoin)
      (Tuple
        (SProxy :: SProxy "isOverCoinSlot'")
        isOverCoinSlot))
    (interval 1))
  false

Here I combine three behaviors (isMouseDown, isOverCoin, and isOverCoinSlot) to make a new behavior (isDragging) that lets me know if the mouse is dragging a coin or not.

If your programming language has functional programming patterns like monad, applicative, and functor, your FRP library will typically create instances for monoid, applicative, semigroup, etc. allowing you to easily combine/compose behaviors declaratively.

Eventually you’ll want to react to a behavior’s value. Your FRP implementation should come with a function that allows you to perform some effectful action over time using the behavior’s value. This effectful action could be updating a button label, moving a game character, logging some information, etc.

void $
  animate
    popMachineState
    (coinCursorAnimation
      [ coin1Img
      , coin2Img
      , coin3Img
      ])

Here I animate the cursor for a coin, depending on the pop machine’s state.

What’s an event?

Events are time-stamped values or (time, value) pairs. You give me a time and I… may or may not have a value for you. In other words, events are discrete variables with respect to time.

💡 The simplest event is just a constant value at a constant point in time.

But you can get as complex as you like. For example, the location of the mouse at the time of a click.

Like behaviors, your FRP library should come with some function that allows you to perform some effectful action, with the event’s value, whenever the event occurs.

void $
  subscribe
    event
    (log `compose` show)

How do I create a behavior from an event?

FRP gets really interesting when you create behaviors from events and vice versa.

let dispensingPopCountEvent = count dispensingPopEvent
let dispensedPopCount = step 0 dispensingPopCountEvent

From the dispensingPopCountEvent, I create a behavior that always has, as a value, the number of pops given out so far.

So I go from this…

To this…

Combining this behavior with others, I can determine which pop to animate on the page when the user inserts a coin.

case count of
  1 -> do
    void(goTo(popStop1Div)(functionalPopImg))
    void(goTo(popStop2Div)(reactivePopImg))
    result <- goTo(popStop3Div)(programmingPopImg)
    when result $
      popMachine.push(WaitingForPopRemoval)
  2 -> -- ...
  3 -> -- ...
  _ ->
    pure(unit)

How do I create an event from a behavior?

Creating events from behaviors opens up a lot of opportunities . Your FRP library should come with functions for turning behaviors into events. One example is the gateBy function.

Let’s say I wanted to go the other way. I have a behavior that holds how many pops have been dispensed so far. From that, I want an event that holds the pop number being dispensed, every time the machine starts dispensing a pop.

let dispensingPopNumber =
      gateBy
        (\ _ state -> state == DispensingPop)
        dispensedPopCount
        popMachine.event

Using the pop machine event as a trigger, I sample the dispensedPopCount behavior, emitting an event with the behavior’s value whenever the pop machine’s state goes to DispensingPop.

How do I combine behaviors?

Combining behaviors to make new behaviors is one of the great strengths of FRP.

Say you have two behaviors, each containing a list of numbers.

let behavior1 = step [] event1.event
let behavior2 = step [] event2.event

let behavior3 = behavior1 `append` behavior2

void $
  animate
    behavior3
    (log `compose` show)

event1.push [1]
event2.push [2]

behavior3 has the value [1,2] and all I had to do was append behavior1 to behavior2.

Say you have two Boolean behaviors…

let behavior3 = (||) `map` behavior1 `apply` behavior2

behavior3 is behavior1 or-ed with behavior2 using functor’s map and applicative’s apply.

Say you have a string behavior and an integer behavior…

let behavior3 =
                    (\ string int ->
                      string `append` show int)
            `map`   behavior1
            `apply` behavior2

You can come up with all sorts of ways to combine behaviors into what you need.

How do I combine events?

Like behaviors, you can combine events in similar ways.

Say you have two events, one and two, and you want another event that occurs whenever one or two occurs.

event1 <- create
event2 <- create

let event3 = event1.event `alt` event2.event

void $
  subscribe
    event3
    (log `compose` show)

event1.push 1
event2.push 2

Using alt, I combined event1 and event2 into event3. When either event1 or event2 occurs, event3 occurs.

FRP is cool.

FRP can be a really powerful way to architect your application using only functions! 🎉 With just behaviors and events, you can declaratively build up a highly stateful application.

For another FRP example, head over to Haskell to JavaScript where I build an on/off button using Haskell’s Reflex.

Are you curious about monads? 🤔 Or maybe you’re further down the rabbit 🐰 hole, looking into applicatives? Does “functor” sound alien 👽 to you?

No worries! 😃

Monad, applicative functor, and functor are just functional programming patterns you can use to deal with effects like lists/arrays, trees, hashes/dictionaries, and even functions.

Functor is the simplest pattern, so it makes sense to start there. As you work your way to monad, you’ll see that functor is the basis for applicative functor which is the basis for monad.

⚠️ If you don’t get the animations, don’t worry. Just focus on the code samples and explanations. The animations are there for some visual intuition. 👍

What’s a functor?

A functor is a list.

map(function)(list) = [function(element) | element <- list]

add1(input) = input + 1

map(add1)([1,2,3])

-- [2,3,4]

The list functor takes a function and applies it to every element inside the list. The function doesn’t have to consider or worry about the list — map handles the list.

A functor is a function.

map(function1)(function2)(input) = function1(function2(input))

sub2(input) = input - 2

map(add1)(sub2)(1)
-- 0

The function functor composes or glues two functions together returning a new function. This new function routes its input through the two functions returning the output of the first function.

A functor is a promise.

map(function)(promise) = fmap(function)(promise)

promise <- async(return 11)

wait(map(sub2)(promise))
-- 9

The promise functor applies a function to its fulfilled input and returns a new promise that will contain the output of the function.

A functor is an effect that you lawfully define map for.

map
  ::       (input -> output) -- Takes a function.
  -> effect(input          ) -- Takes input inside an effect.
  -> effect(         output) -- Returns output inside an effect.

In general, a functor is just map defined for some effect. The map function

• takes a function input -> output ,
• takes input for that function stuck inside an effect effect(input) ,
• passes the input to the function,
• collects the function’s output,
• and returns the output stuck inside the effect effect(output) .

Wait, what do you mean by “lawfully define?”

The map definition must obey the functor laws.

How many functor laws are there?

There are two laws your map definition must obey.

Okay, what’s the first law?

If you pass identity to map, map’s output must equal its input.

list = [1,2,3]

identity(input) = input

list == map(identity)(list)
-- True

Hmm, what’s the second and last law?

If you compose two or more functions and pass that to map, map’s output must equal the output of composing multiple calls of map together— one for each function.

times3(input) = input * 3

composition(input) = add1(sub2(times3(input)))

composition(1)
-- 2

list = [1,2,3]

map(composition)(list) == map(add1)(map(sub2)(map(times3)(list)))
-- True

One call to map using composition and list equaled three calls to map using add1, sub2, and times3 and list.

So functor is an interface?

Yes. If you define a lawful version of map for some effect, it is an instance of functor or mappable. map is an overloaded function that is defined differently for each type of effect you define it for.

If you’ve used the usual map for lists/arrays— found in most standard libraries — you’ve been using functors all along. 😺

What do you mean by effect?

List/Array is an effect. Tuple/Struct/Record is an effect. Future/Promise is an effect. Function is an effect. Tree is an effect. HashMap/Hash/Dictionary is an effect. Maybe/Optional/Nullable is an effect. Either (or the more specialized try) is an effect. There are many effects. These are some of them.

Ask what an effect is and you’ll see or hear “context”, “functorial context”, “container”, “container and payload”, “wrapper”, “box”, “computation”, “ambiguous computation”, “structures”, “data structures”, “nondeterminism”, “nondeterministic”, “type constructors”, “side-effects”, “a side-effect made explicit”, “impure”, and/or “not pure”. Phew.

The definition of effect is “power to bring about a result”. This is true for anything I’ve seen called an effect. They have the power or capability to bring about a result but may not always. For example, the empty list/array or nothing/none/null for maybe/optional/nullable.

I still don’t get functor.

A functor lifts or upgrades a function from one that cannot operate on an effect to one that can work on a single effect, leaving the effect intact after the function is done.

In terms of an interface, if you want some effect to be a functor, you have to (lawfully) define map for it.

Can map accept a function with more than one parameter?

If some function takes more than one parameter and you map it over some functor, it will be partially applied and stuck in the effect.

Take lists for example.

add(left)(right) = left + right

map(add)([1,2,3])
-- [ add(1),
--   add(2),
--   add(3) ]

add was partially applied to 1, 2, and 3 making for three partial applications of add stuck inside the list. Partially applied meaning the function is waiting on its other parameters. add(1) for example is waiting on one more number.

[ add(1),
  add(2),
  add(3) ]

⚠️ At this point you’re stuck. You can’t feed this result back into map in order to supply more input to the adds. map doesn’t take partially applied functions — waiting inside an effect/list — so you’ll need applicative functor to work with this result.

What are applicative functors?

An applicative functor is a list.

pure(input) = [input]

apply(functions)(list) =
  [ element | function <- functions,
              element  <- map(function)(list)
  ]

apply(pure(add1))([1,2,3])
-- [2,3,4]

apply(apply(pure(add))([1,2,3]))([4,5,6])
-- [5,6,7,6,7,8,7,8,9]

apply(map(add)([1,2,3]))([4,5,6])        
-- [5,6,7,6,7,8,7,8,9]

It returns [5, 6, 7, 6, 7, 8, 7, 8, 9] because it adds 1 to 4, 5, and 6, adds 2 to 4, 5, and 6, and then adds 3 to 4, 5, and 6.

💡 Instead of thinking about a list as a container for values, think of it as a nondeterministic value or put another way, a choice.

The list applicative functor computes all of the possible combinations or choices when sequencing or composing lists. You can represent this as a tree.

Anyway, notice how I had to use one apply for every parameter add takes. One for the first parameter and another one for the second parameter.

The pure and first apply call wrapped three partially applied adds inside a list but you can substitute the pure and one apply call with map as using add with map also wraps three partially applied adds inside a list. We saw this up above with functor.

apply(pure(add))([1,2,3])
-- [ add(1),
--   add(2),
--   add(3) ]

map(add)([1,2,3])
-- [ add(1),
--   add(2),
--   add(3) ]

🤔 So far all of the examples had non-empty lists but what happens if any one list is empty?

[   ] `apply` [1,2,3] `apply` [4,5,6]
-- []
[add] `apply` [     ] `apply` [4,5,6]
-- []
[add] `apply` [1,2,3] `apply` [     ]
-- []

You get an empty list. Tracing the implementation, you can see that if any one list is empty, it propagates out. Doesn’t matter what the other lists had, you’ll always get an empty list if any one of the lists are empty.

If any of the effects are empty or failed, for the list effect and others (like maybe or either), the first occurrence will spill out in the end. This works out nicely as you don’t have to consider the empty case when applying lists or even worse, experience a crash because you ended up with an empty list somewhere.

💡One of the big aspects of applicative functor is that the effects play out before the lifted/upgraded function can do its thing. Applicative functor is like the Ronco — set it and forget it — showtime rotisserie 🍗 of functional programming patterns. Once we’ve kicked off the process, we can only wait for the end result.

There’s no picking and choosing what’s next based on what’s already occurred. We don’t get to look at an intermediate result and make a decision. It’s been said that applicative functor is batch versus interactive processing as is the case with monads.

Let’s say we have a function called if_x_then_y_else_z (example adapted from Applicative Programming with Effects, Conor McBride and Ross Paterson. in Journal of Functional Programming 18:1 (2008), pages 1–13).

if_a_then_b_else_c(a)(b)(c) = if a then b else c

pure(if_a_then_b_else_c) `apply` x `apply` y `apply` z

It takes in three effects and depending on x’s result, it either picks the result from y or z. Since we’re talking about lists at this point, let’s use the list applicative functor.

if_x_then_y_else_z([True])(["y result"])(["z result"])
-- ["y result"]

if_x_then_y_else_z([False])(["y result"])(["z result"])
-- ["z result"]

So if an item of x is True, we go with y’s item else we go with z’s.

if_x_then_y_else_z([True])(["y result"])(["z result"])
-- ["y result"]

For the inputs

• [True]
• ["y result"]
• and ["z result"]

it doesn’t matter what z holds as it’ll never be used. But notice what happens when z is empty.

if_x_then_y_else_z([True])(["y result"])([])
-- []

You get an empty list even though the z list isn’t needed since x holds a single True. But like I wrote up above, if any of the lists are empty, the result will be empty too.

You could try to get around this by lifting/upgrading a function that returns a list.

if_x_then_y_else_z(x)(y)(z) =
  apply(pure(\ a -> if a then y else z))(x)

if_x_then_y_else_z([True])(["y result"])([])                           
-- [["y result"]]

⚠️ But now you’re stuck. You have nested effects or in this case, nested lists. Later on, you’ll see how the list monad deals with this situation.

💡The big thing to remember with applicative functor is that the lifted/upgraded function cannot change/influence the shape of the effect at any time. For list, the shape would be the size. For maybe the shape would be just or nothing. For either the shape would be left or right.

Without running the applicative functor, you can determine the resulting shape just by looking at the shape of the effects given. Given an empty list? You’re going to get an empty list. Given [1,2] and [3,4,5]? You’re going to get back a list with six items.

With monads it’s different. They can change the shape because they can look at the intermediate results and decide what to do next.

An applicative functor is a function.

pure(function)(ignore) = function

pure(add1)(Nothing)(0)
-- 1

apply(wrapped_function)(function)(input) =
  map(wrapped_function(input))(function)(input)

apply(pure(add1))(add1)(1)
-- 3

(pure(add) `apply` add1 `apply` add1)(1)
-- 4

The pure definition for functions is just the constant (const) function. The constant function takes two parameters and returns the first one ignoring the second one. So calling pure(add1)(Nothing) wraps and then unwraps add1. You can unwrap using any input you’d like as constant will just ignore it.

pure(add1)("Ignore this?")(1)
-- 2

pure(add1)(concat ["Ignore"," this?"])(1)
-- 2

Notice how I chained as many calls to apply as how ever many parameters the function took. I used one apply for add1 and two calls of apply for add.

add_x_y_z(x)(y)(z) = add(add(x)(y))(z)

add_x_y_z(2)(2)(2)
-- 6

(pure(add_x_y_z)
`apply` add1
`apply` add1
`apply` add1)(1)
-- 6

The three calls to apply — one for x, one for y, and one for z — returns 6 because

• 1 gets added to 1 making x equal 2
• 1 gets added to 1 making y equal 2
• 1 gets added to 1 making z equal 2
• and finally x, y, and z get added together for a total of 6.

apply(pure(add_x_y_z))(add1)(1)(2)(3)
-- 7

add_x_y_z(add1)(2)(3)
-- 7

You don’t have to chain a call to apply for every argument. In this example, I modified the x parameter with add1 but passed 2 as y and 3 as z directly to add_x_y_z.

add1(input) = 1 + input
sub2(input) = 2 - input                                 
sub3(input) = 3 - input
                                 
(pure(add_x_y_z) `apply` add1 `apply` sub2 `apply` sub3)(4)
-- 2

add1(4) + sub2(4) + sub3(4)
-- 2

(1 + 4) + (2 - 4) + (3 - 4)
-- 2

If you do modify every parameter with apply, the resulting function will only accept one input which will go to every modified parameter. In this example, 2 went to every modified parameter of add_x_y_z.

first  = \ (a,b,c) -> a                                                               
second = \ (a,b,c) -> b                                                              
third  = \ (a,b,c) -> c 

new_add_x_y_z =
  pure(add_x_y_z) `apply` first `apply` second `apply` third         

new_add_x_y_z(1,2,3)
-- 6

If the form of your input data doesn’t match the parameter signature of your function, using apply to compose your function with some other functions comes in handy. In this example, the data was in a tuple so I composed add_x_y_z with first, second, and third to extract and then add together 1, 2, and 3.

extract_then_add_x_y_z(t) =
  add_x_y_z(first(t))(second(t))(third(t))               

extract_then_add_x_y_z(1,2,3)
-- 6

Granted, I could’ve done it like the example above but applicative functor gives us a nicely generalized interface for modifying the input to some function with other functions.

first  = \ (a,b) -> a
second = \ (a,b) -> b

new_add_x_y_z = pure(add_x_y_z) `apply` first `apply` second

new_add_x_y_z(1,2)(3)                                         
-- 6

If say, part of my data was in a tuple, I only have to reason about apply and pure instead of coming up with a specific function to handle this particular scenario.

An applicative functor is a functor that you lawfully define pure and apply for.

pure
  :: input         -- Takes some input.
  -> effect(input) -- Returns it inside an effect.

apply
  :: effect(input -> output) -- Takes a function in an effect.
  -> effect(input          ) -- Takes input in an effect.
  -> effect(         output) -- Returns output in an effect.

In general, an applicative functor is a functor that you define apply and pure for. The apply function

• takes a function inside an effect effect(input -> output),
• takes input for that function inside an effect effect(input),
• applies the function to the input,
• and returns the function’s output inside the effect effect(output) .

💡 Compare it to map and you’ll see the subtle change — the function is now in the effect too.

map
  ::       (input -> output) -- Takes a function.
  -> effect(input          ) -- Takes input inside an effect.
  -> effect(         output) -- Returns output inside an effect.

apply
  :: effect(input -> output) -- Takes a function in an effect.
  -> effect(input          ) -- Takes input in an effect.
  -> effect(         output) -- Returns output in an effect.

👀 Look again but in this condensed form.

map   ::  (i -> o) -> e(i) -> e(o)
apply :: e(i -> o) -> e(i) -> e(o)
--       ^ The big difference.

That’s the main and only difference between apply and map .

Lawfully, meaning applicative functor has laws too?

Yes. There are four applicative functor laws.

So applicative functor is an interface too?

Yes. If there are lawful definitions of pure and apply for some functor, it is an instance of applicative functor. In other words, applicative functor extends the functor interface with pure and apply.

I still don’t get applicative functor.

Applicative functor picks up where functor leaves off. Functor lifts/upgrades a function making it capable of operating on a single effect. Applicative functor allows the sequencing of multiple independent effects. Functor deals with one effect while applicative functor can deal with multiple independent effects. In other words, applicative functor generalizes functor.

In terms of an interface, applicative functor adds pure and apply to functor’s map.

What do you mean by independent effects?

Independent meaning some effect does not rely on the outcome of some other effect.

x = [1,2]
y = [3,4]
z = [5,6]

pure(add) `apply` (pure(add) `apply` x `apply` y) `apply` z  
-- [9,10,10,11,10,11,11,12]

In this example, we sequence three effects or lists. Neither x, y, nor z rely on the outcome of any other. Since they’re all independent, we could process the final result in parallel or simultaneously. This is one of the advantages to applicative functor.

[ 1+3+5=09,
  1+3+6=10,
  1+4+5=10,
  1+4+6=11,
  2+3+5=10,
  2+3+6=11,
  2+4+5=11,
  2+4+6=12 ]

Now say we lift/upgrade the following function for the list instance.

add1_inside_effect(input) = pure(input + 1)

It will return a dependent effect/list dependent on some item input from some other list.

pure(add1_inside_an_effect) `apply` x                    
-- [[2],[3]]

pure(add) `apply` (pure(add1_inside_an_effect) `apply` x)
-- error!

Applicative functor only deals with independent effects. If you have a dependent effect, you’ll need monads as you’ll see next.

What is a monad?

A monad is a list.

join(nested_lists) =
  [element | list <- nested_lists, element <- list]

join([[1], [2, 3], [4, 5, 6]])
-- [1, 2, 3, 4, 5, 6]

join(apply(pure(\ x -> [x + 1, 1]), [1,2,3]))
-- [2, 1, 3, 1, 4, 1]

join(
  apply(
    pure(\ x -> [2, x * 3, x * 4]))(
    join(
      apply(
        pure(\ x -> [x + 1, 1]))(
        [1,2,3]))))
-- [2,6,8,2,3,4,2,9,12,2,3,4,2,12,16,2,3,4]

The big and only addition for the monad interface is join. join flattens or better put, peels off an effect from two nested effects. For the list instance, join is just concat.

Join only deals with nested effects that are the same type and nested one level deep. So for example, [[1], [3,4]], just(just(1)), right(right(2)) but not [just(1), just(left(1))], [1, [2]], [[[1]]], etc.

if_x_then_y_else_z =
  pure(\ a -> if a then y else z) `apply` x

if_x_then_y_else_z([True])(["y result"])([])                           
-- [["y result"]]

When we previously lifted/upgraded a function that returned a list (to get around z being empty), we ended up with a nested list. Back then we were stuck but join allows us to keep on truckin’ 🚚. Now you can pick either the y or z list based on the items in x and not end up with a nested list.

if_x_then_y_else_z(x)(y)(z) =
  join(pure(\ a -> if a then y else z) `apply` x)

if_x_then_y_else_z(
  [True,False,False,True])(
  ["y result"])(
  ["z result"])
-- [ "y result",  True  so return y.
--  "z result",   False so return z.
--  "z result",   False so return z.
--  "y result" ]  True  so return y.

💡 Therein lies the power of monads, they allow us to pick the next effect based on the result from a previous effect. In other words, monad allows us to sequence dependent effects or better put, sequence functions that return effects.

⚠️ Note that “pick the next effect” doesn’t mean you can, at some point, change the type of effect you return. For example, you can’t suddenly decide to return a maybe if you’re operating in the list monad. A monad is also a functor, so in the end, the effect must remain intact with only its results potentially altered.

A monad is a function.

join(wrapped_function)(input) =
  wrapped_function(input)(input)

join(apply(pure(add))(add1))(1) 
-- 3

add(add(1)(1))(1)
-- 3

add(2)(1)
-- 3

(1 + 1) + 1
-- 3

divide(numerator)(denominator) = numerator / denominator

join(
  apply(
    pure(divide))(
    join(
      apply(
        pure(add))(
        add1))))(2)
-- 2.5

divide(
  add(
    add(
      1)(
      2))(
    2))(
  2)
-- 2.5

divide(
  add(
    3)(
    2))(
  2)
-- 2.5

divide(
  5)(
  2)
-- 2.5

(((1 + 2) + 2) / 2)
-- 2.5

The function monad allows you to sequence or compose functions together. The first function in the chain can only take one parameter and the rest have to take two parameters.

After you’re done composing functions together using join, apply, and pure, the returned function will only take one input. This single input will start a chain reaction.

• The first function takes only one parameter.
• It receives the input and returns some output.
• The second function takes two parameters.
• It receives the output from function one, the input, and returns some output.
• The third function takes two parameters.
• It receives the output from function two, the input, and returns some output.
• The fourth function…and on and on for how ever many functions you sequenced.

A monad is an applicative functor that you lawfully define join for.

join
  :: effect(effect(data))
  -> effect(data)

In general, a monad is just an applicative functor you define join for.

So monads are just applicative functors with join added to the interface?

Yes.

How many laws are there for monad?

There are three monad laws.

What about return and bind?

Bind is just a convenience function that composes join, apply, and pure.

bind(effect)(function) = join(apply(pure(function))(effect))

[1,2,3] `bind` \ x -> [x + 2]
-- [3,4,5]

[1,2,3] `bind` \ x -> [x + 2] `bind` \ y -> [y * 3]       
-- [9,12,15]

[1,2,3] `bind` \ x -> pure(x + 2) `bind` \ y -> [y * 3, 0] 
-- [9,0,12,0,15,0]

(add1 `bind` add `bind` divide)(2)
-- 2.5

Or if you prefer, bind composes join and map together.

bind(effect)(function) = join(map(function)(effect))

[1,2,3] `bind` \ x -> pure(x + 2) `bind` \ y -> [y * 3, 0] 
-- [9,0,12,0,15,0]

return is just pure.

return = pure

Can you summarize them for me?

• Functor lifts or upgrades a function, allowing it to operate on a single effect, leaving the effect intact after it’s done. It requires a lawful map definition.
• Applicative functor builds on or generalizes functor, allowing you to sequence multiple independent effects. It requires a lawful pure and apply definition.
• Monad builds on or generalizes applicative functor, allowing you to sequence independent and/or dependent effects. It requires a lawful join definition.

map   ::  (i ->   o ) -> e(i) -> e(o) -- Functor
apply :: e(i ->   o ) -> e(i) -> e(o) -- Applicative
bind  ::  (i -> e(o)) -> e(i) -> e(o) -- Monad
         ^      ^

If you’d like to see what you can do with functors, applicatives, and monads, check out Movie Monad and Gifcurry — two desktop GUI apps created with Haskell, a purely functional programming language.

For more information about functors, applicatives, monads, and other functional programming patterns, take a look at Typeclassopedia by Brent Yorgey.

For the upcoming release of Gifcurry — an open-source, video-to-GIF maker — a completely custom theme was made using CSS and Haskell. The new theme will help maintain a more consistent look and feel across platforms and for Linux — across distros. The theme also ensures the need for only one set of custom icons.

Creating a GTK desktop app and styling it like you would a web application is a great alternative to frameworks like Electron. You can reuse your CSS knowledge and ship a cross-platform product with reduced system requirements. Of course Haskell isn’t required, as you can create and style GTK apps without it, but why would you want to? 😛

The CSS-like syntax will hopefully be much more familiar to many people, lowering the barrier for custom theming. — https://developer.gnome.org/gtk3/stable/gtk-migrating-GtkStyleContext-css.html

Supporting Older GTK Versions

When building a custom theme for your GTK application, you’ll have to consider supporting older versions of GTK. If you have Ubuntu 14.04 users for instance, you’ll need to support the GTK 3.10 CSS file format. Ubuntu 16.04 users will need support for GTK 3.18.

Gifcurry aims to support GTK 3.10 all the way up to GTK 3.24 and beyond. Between 3.10 and now, there are some commonalities but big changes occurred in 3.18, 3.19, and 3.20. Gifcurry applies a base styling and then detects the machine’s GTK version applying more styling rules as the version number goes higher.

Some of the big changes include:

• Element selectors like GtkButton turning into button.
• Class selectors turning into element selectors like GtkSpinButton .entry turning into spinbutton entry.
• Pseudo classes like :insensitive becoming :disabled.
• Non-standard properties like -gtk-icon-shadow added in later versions.

You can combine most of the differences in the same CSS file and there won’t be any conflicts or exceptions raised.

entry selection,
.entry:selected {
  background-color: #000;
}

GTK will raise exceptions, when parsing your CSS data, for situations like an unknown property or incorrect syntax. This of course doesn’t happen for the web where you browser crashes because of a bad CSS file. Nonetheless, you should test any rules you add. GTK will issue warnings for deprecated rules so be sure to watch the standard streams.

Deciding which CSS Rules You Need

There are a lot of elements and states to consider when creating a whole theme. Depending on what widgets you use, you can get away with not specifying everything.

What I recommended is to select your favorite GTK theme as your system theme. Afterwards, start your app from the terminal specifying you want the interactive debugger.

$ GTK_DEBUG=interactive my-gtk-app

This GUI debugger allows you to inspect any element/node and see what its CSS properties, children, parent, style classes, state, and more are. You can change the theme on the fly and also update the CSS rules as the app is running. It is similar to Chrome’s DevTools but you can’t point-and-click update the CSS properties for example. To update the CSS, you’ll have to click the CSS tab and write out your changes in the provided text box. As you write out your rules, it will underline any errors and/or warnings.

Using the interactive debugger, you can quickly build up the CSS rules that make up your theme. After you get it looking pixel perfect, select the visual tab and change the theme. Look for any breakages and patch your rules as needed. The more themes you test against, the more your app theme will look consistent no matter what the GTK system theme is.

After you’re finished with one GTK version, switch to another and continue this same workflow. I like to test GTK 3.22, 3.18, and 3.10 simultaneously using two virtual machines running Ubuntu 14.04 and Ubuntu 16.04.

Generating the CSS Data

You have a few options for getting the CSS rules to GTK. You can write plain CSS, stick it in a .css file, and apply it via the GTK API.

button {
   color: white;
   background: #000;
}

…

styleFile 
  <- getDataFileName "data/style.css"

GI.Gtk.cssProviderLoadFromPath
  provider
  (Data.Text.pack styleFile)

GI.Gtk.styleContextAddProviderForScreen
  screen
  provider
  cssPriority

Another option is to use your favorite CSS preprocessor, stick it into your build chain, generate the file, and then apply that via the GTK API. Since we’re using Haskell, we can use Clay — “a CSS preprocessor […] implemented as an embedded domain specific language (EDSL) in Haskell.”

The nice thing about using Clay is that we don’t have to stick it into the build process, generate a .css file, and load it via the GTK API. Clay allows us to stay in Haskell, generate the CSS rules at run time, and apply the rendered output via cssProviderLoadFromData.

let css =
        encodeUtf8 $
          render $
            button ? do
              color white
              background "#000"

GI.Gtk.cssProviderLoadFromData
    provider
    css

GI.Gtk.styleContextAddProviderForScreen
    screen
    provider
    cssPriority

The End

If you’ve thought about creating a desktop app, GTK is a great solution that allows fully customizable styling. Using CSS, you’re in complete control of the look, feel, and branding of your app just like you would be with the web. The CSS is slightly different but you’ll hardly notice. And if you need something stronger than styling, you can always create your own custom widget.

Interested in GTK apps? Take a look at Movie Monad. Need a video-to-GIF maker? Download Gifcurry. Enjoyed this article? Show your support by clicking the applause button. Thanks!

✉️ Subscribe to CodeBurst’s once-weekly Email Blast, 🐦 Follow CodeBurst onTwitter, view 🗺️ The 2018 Web Developer Roadmap, and 🕸️ Learn Full Stack Web Development.

How to Style Your GTK App with CSS and Haskell was originally published in codeburst on Medium, where people are continuing the conversation by highlighting and responding to this story.

GTK, if you’re unfamiliar with it, is a library for creating graphical widgets for the desktop. These widgets can take in user input and/or show application output. GTK comes with a nice selection of widgets. Widgets range from the humble checkbox to a full-blown file explorer. For the most part, you’ll never need to create your own widget but sometimes what’s in stock isn’t enough.

Gifcurry — a cross-platform GIF creator slash video editor made with Haskell — needed a custom widget to interface with user selected time slices. There is the main time slice of the GIF and the time slices for each dynamic text overlay added.

The widget consists of two major areas. The top area shows a zoomed-in view of the GIF time slice itself. The bottom area shows all time slices as they fall between the beginning and end of the video. In both parts, the white line represents the current video’s position. The top part also gets the video position clock. For convenience, the user can click anywhere on the GIF time slice to change the video’s current position. As the input changes, the widget updates to match giving immediate feedback.

The Draw Area Widget

The draw area widget is the foundation for any fully custom widget.

The GtkDrawingArea widget is used for creating custom user interface elements. It’s essentially a blank widget; you can draw on it. — https://developer.gnome.org/gtk3/stable/GtkDrawingArea.html

After you create the draw area, be sure it’s application paintable. Make sure to apply the event masks you wish to capture like a mouse button click.

GI.Gtk.widgetAddEvents
  myWidget
  [GI.Gdk.EventMaskAllEventsMask]

The Draw Widget Queue

GTK takes a lazy approach to drawing widgets. It will redraw your widget when some or all of it has been invalidated like being covered up by another window. To keep a constant render loop going, you’ll have to force a redraw by scheduling it.

GI.Glib.timeoutAdd
  GI.Glib.PRIORITY_DEFAULT
  1 $
    GI.Gtk.widgetQueueDraw myWidget
    return True

Once queued, your widget will receive an onWidgetDraw event. This event is your chance to update any of your widget’s graphics.

The On Draw Event

GTK lets you register a callback for a widget’s onWidgetDraw event. Inside the callback is where you’ll draw on your widget. To draw on your widget, you’ll need another library known as Cairo.

Cairo is a 2D graphics library with support for multiple output devices. — https://cairographics.org/

There are two major Haskell projects that produce bindings for GTK and its related libraries. There is the older one, gtk2hs, and the newer one, haskell-gi. Each comes with its own Cairo binding. For the draw calls, you’ll need the older one (cairo) provided by gtk2hs.

The newer binding (gi-cairo) doesn’t bind to most of the Cairo API as haskell-gi generates the binding automatically using GObject Introspection but the introspection data for Cairo is incomplete. If you do use gi-cairo, there is a workaround to bridge its binding to the more hand-rolled binding provided by gtk2hs.

Nevertheless, your registered callback will receive a context. You’ll pass this context off to Cairo and perform all your drawing calls in the Render monad.

GI.Gtk.onWidgetDraw
  myWidget $
    \ context-> do

If you want to call something in the IO monad, don’t forget the liftIO function.

(r, g, b) <-
  liftIO $
    getRgb color

If you’ve ever done any HTML5 canvas drawing, you’ll be familiar with the context.

document.getElementById('my-canvas').getContext('2d');

Relating it to GTK, the GtkDrawingArea is the canvas and the context is…well…the context. Anyway, the context isn’t all that important. It can, however, be a stumbling block when trying to integrate haskell-gi’s gi-cairo with gtk2hs’ cairo.

Like the HTML5 canvas API, Cairo comes with all the primitives you’d expect. You can draw lines, rectangles, ellipses, and even text (you’ll need Pango for advanced text rendering). Gifcurry uses a PNG pattern fill to color the time slices. The purple area is the GIF time slice and the green is a text overlay time slice.

GRC.rectangle x y w h        
GRC.setSourceRGBA 0.1 0.1 0.1 1.0
GRC.fill

The On Widget Event

If your widget is only to show application output, then you’re done at this point and can ship it. If you want to capture user input, you’ll need to register a callback for the event(s) you wish to deal with.

GI.Gtk.onWidgetButtonPressEvent
  myWidget $
    \ eventButton-> do

Gifcurry captures the left mouse button click to update the video’s current position. This allows users to bounce around the video. Using a little algebra and geometry, Gifcurry translates the mouse’s 2D spatial coordinates to the video’s 1D time.

The End

It’s not everyday that someone uses GTK, Haskell, and needs a custom widget. But for those that do, your only limitation now is your imagination. If you only need a slightly modified widget, consider using CSS. GTK widgets can be styled with CSS (just like the web) for a truly custom look. Gifcurry uses CSS to style its about dialog.

If you haven’t tried GTK but are into native-desktop, front-end development, give it a spin. You can achieve the same look and feel as Electron and spare your users from downloading more RAM. And while you’re at it, give Haskell a try if you haven’t. Haskell works for you so you can spend more time creating great widgets.

Interested in GTK apps? Take a look at Movie Monad. Need a video to GIF maker? Download Gifcurry. Enjoyed this article? Clap it up. Thanks!

✉️ Subscribe to CodeBurst’s once-weekly Email Blast, 🐦 Follow CodeBurst on Twitter, view 🗺️ The 2018 Web Developer Roadmap, and 🕸️ Learn Full Stack Web Development.

How To Build A Custom GTK Widget With Haskell was originally published in codeburst on Medium, where people are continuing the conversation by highlighting and responding to this story.

You’ve modeled your life around Kleisli composition. On your right arm is a tattoo that reads, “point free or die.” You can tie the knot in your sleep. Zygohistomorphic prepromorphism is your go-to recursion scheme. You looked out from atop the Haskell pyramid and found the view boring. Now comes the hard part — distributing your Haskell app to Linux users.

Once that last commit goes in, it’s time to get your app out there by opening up a distribution channel. One viable Linux app distribution channel is Flathub.

Flathub aims to be the place to get and distribute apps for Linux. It is powered by Flatpak which allows Flathub apps to run on almost any Linux distribution. — https://flathub.org/about

To add your app to Flathub, you must first make a Flatpak manifest. I’ll make this concrete by following along with everyone’s favorite functional video player Movie Monad and its induction into Flathub.

The Setup

First things first, get a working virtual machine of the latest Fedora up and running. Geared for Flatpak, Fedora will simplify things.

While Flatpak is not officially affiliated with the Fedora Project, or GNOME Foundation, it is perhaps best supported by Fedora and the GNOME desktop environment. This is because Fedora releases 23 and later have all had Flatpak in their official repositories. The GNOME Software application also has support for installing Flatpaks. — https://fedoraproject.org/wiki/Flatpak

With the virtual machine running, make sure you can build and run your Haskell app on Fedora — outside of the Flatpak sandbox system. Identify any issues you come across and any packages you had to install.

The Manifest

The manifest is a JSON file that describes the app, its run time, its permissions, its dependencies, its build procedure, and the command needed to run it.

There are different available run times that come with their own set of packages. Choose the run time that provides the greatest number of dependencies your app needs. For anything needed outside the run time, you’ll have to provide it yourself inside the modules section of the manifest.

Since we’re dealing with Haskell, you’ll need GHC to build your app inside the sand-boxed build environment. Flatpak doesn’t make any demands about what must be built from source. Flathub, however, does require that you build your app from source.

Note the prefix used in the image above. Everything you add to modules should go under “/app”. This is a Flathub rule.

Inside the sand-boxed build environment, we have no network access. Everything that needs to be downloaded can only be downloaded by flatpak-builder. So anything we want downloaded and available to us inside the sandbox has to go under sources for each module. This makes building Haskell apps much more complicated as it rules out options like Stack or cabal-install.

To get around the lack of network access, we’ll have to perform some of what Stack and Cabal does. The first thing we need is the list of dependencies we’ll have to download and build. I recommend building your app (outside the Flatpak system) with Cabal — using a fresh sandbox — and making note of which dependencies it builds, their exact version numbers, and the order it builds them in.

The order is important. I don’t know of any Stack or Cabal command that will list the dependencies, with their exact version number, in dependent order. We need the dependencies in order as flatpak-builder runs the modules in the order you list them. If you attempt to build Cabal package B but it depends on A and A is listed below B, B will fail to build and flatpak-builder will exit.

With the list of dependencies (and their version numbers) sorted by dependence, we need to generate the list of modules. We could do this by hand but instead we’ll script it.

The script up above downloads the dependency from Hackage, calculates it hash, and outputs the JSON block to be copied into the manifest for each dependency we feed it. For most Cabal packages, the build commands are the same using the typical setup, configure, build, and install procedure.

For some Cabal packages, you’ll run into revisions. The tar files downloaded from Hackage are not up-to-date with any revisions. In some cases, this will cause the build to break and you’ll have to apply the revisions yourself. You could download the revisions from Hackage (listing the files in the sources section) and overwrite the revised files. Instead, I used sed as you can see in the image above. In this particular case, I had to increase the upper bound limit from <4.9 to <5 for base.

When it comes time to build and install your app, you must copy the AppData, desktop, and icon file into their appropriate places under /app.

For each file, it must be in reverse domain name notation. So

• my-app.appdata.xml becomes tld.domain.my-app.appdata.xml
• my-app.desktop becomes tld.domain.my-app.desktop
• and my-app.svg becomes tld.domain.my-app.svg.

If your app lives on GitHub, you could use com.github.username.my-app.

Inside the AppData file, the <id/> section must also use the reverse domain name notation. Flathub has a quirk where the <id/> must end in .desktop. If it doesn’t, your app will not show up on the Flathub website but will still appear in GNOME software. Normally, the <id/> section doesn’t need to end with .desktop. I believe this is fixed now, however.

While you’re editing your AppData, run it through appstreamcli validate. This will point out any errors present and make suggestions.

Make sure the Icon= key value entry in the desktop file also uses the reverse domain name notation.

In the same module block that builds and installs your app, you’ll want to specify a post-install procedure. It is here that you can remove any files not necessary to run your app. This will reduce the final file size making for a quicker download of your app from Flathub.

flatpak-builder my-app tld.domain.my-app.json --force-clean --install
flatpak run tld.domain.my-app

With your manifest complete, it is now time to build and run it. If you need to debug it, you can do the following. This will give you a shell inside the sand-boxed environment.

flatpak-builder -- run my-app tld.domain.my-app.json sh

The Pull Request

You’ve written your manifest and have tested it on your local virtual machine running Fedora. If everything works, you can now fork Flathub and submit your pull request to add your app. Make sure to title the pull request “Adds tld.domain.my-app”.

After you submit your pull request, the friendly Flathub maintainers will review it, close it, open up a repository for it under Flathub, and give you write access to the new repository. With this new repository, you can update the manifest with any version changes necessary. Each time you push to master, a build of your Flatpak will start. Check Buildbot to make sure the build succeeded and deployed.

flatpak remote-add flathub https://flathub.org/repo/flathub.flatpakrepo
flatpak install flathub tld.domain.my-app

Using the commands above, any Flatpak user can now install your app.

The End

As of this writing, I only know of two Haskell apps in Flathub — Movie Monad being the more complicated one to build. If you add your Haskell app, be sure to let me know in the comments below.

Flatpak not your thing? Want to be in more app stores? Check out How to Snap your Awesome (Haskell) App.

Like Haskell apps? Check out Gifcurry and Movie Monad — you’ll love ’em.

Before we get started, I made a tool (here’s the source) that runs LDA right inside your browser (it’s pretty neat). Be sure to have that open as I go along, it will make things a lot clearer.

All of the emoji I use come from this page. Just select any one emoji and copy it into the input boxes. If you don’t see the emoji, try using Firefox version 50 or greater.

What is LDA?

Latent Dirichlet Allocation (LDA) is a “generative probabilistic model” of a collection of composites made up of parts. Its uses include Natural Language Processing (NLP) and topic modelling, among others.

In terms of topic modelling, the composites are documents and the parts are words and/or phrases (phrases n words in length are referred to as n-grams).

But you could apply LDA to DNA and nucleotides, pizzas and toppings, molecules and atoms, employees and skills, or keyboards and crumbs.

The probabilistic topic model estimated by LDA consists of two tables (matrices). The first table describes the probability or chance of selecting a particular part when sampling a particular topic (category).

The second table describes the chance of selecting a particular topic when sampling a particular document or composite.

Take the image up above for example. We have four emoji sequences (the ‘composites’) and three types of emoji (the ‘parts’).

The first three documents have ten of only one type of emoji, while the last document has ten of each type.

After we run our emoji composites through LDA, we end up with the probabilistic topic model you see above.

The left table has ‘emoji-versus-topics’, and the right table shows ‘documents-versus-topics’. Each column in the left table and each row in the right table sums to one (allowing for some truncation and precision loss).

So if I were to sample (draw an emoji out of a bag) Topic 0, I’d almost certainly get the avocado emoji. If I sampled Document 3, there’s an equal (or ‘uniform’) probability I’d get either Topic 0, 1, or 2.

The LDA algorithm assumes your composites were generated like so:

1. Pick your unique set of parts.
2. Pick how many composites you want.
3. Pick how many parts you want per composite (sample from a Poisson distribution).
4. Pick how many topics (categories) you want.
5. Pick a number between not-zero and positive infinity and call it alpha.
6. Pick a number between not-zero and positive infinity and call it beta.
7. Build the ‘parts-versus-topics’ table. For each column, draw a sample (spin the wheel) from a Dirichlet distribution (which is a distribution of distributions) using beta as the input. Each sample will fill out each column in the table, sum to one, and give the probability of each part per topic (column).
8. Build the ‘composites-versus-topics’ table. For each row, draw a sample from a Dirichlet distribution using alpha as the input. Each sample will fill out each row in the table, sum to one, and give the probability of each topic (column) per composite.
9. Build the actual composites. For each composite, 1) look up its row in the ‘composites-versus-topics’ table, 2) sample a topic based on the probabilities in the row, 3) go to the ‘parts-versus-topics’ table, 4) look up the topic sampled, 5) sample a part based on the probabilities in the column, 6) repeat from step 2 until you’ve reached how many parts this composite was set to have.

Now we know this algorithm (or generative procedure/process) is not how documents (such as articles) are written, but this — for better or worse — is the simplified model LDA assumes.

What is the Dirichlet distribution?

A bit about the Dirichlet distribution before we move on.

What you see in the animation above are iterations of taking 1000 samples from a Dirichlet distribution using an increasing alpha value.

The Dirichlet distribution takes a number (called alpha in most places) for each topic (or category). In the GIF (and for our purposes), every topic is given the same alpha value you see displayed. Each dot represents some distribution or mixture of the three topics like (1.0, 0.0, 0.0) or (0.4, 0.3, 0.3). Remember that each sample has to add up to one.

At low alpha values (less than one), most of the topic distribution samples are in the corners (near the topics). For really low alpha values, it’s likely you’ll end up sampling (1.0, 0.0, 0.0), (0.0, 1.0, 0.0), or (0.0, 0.0, 1.0). This would mean that a document would only ever have one topic, if we were building a three topic probabilistic topic model from scratch.

At alpha equal to one, any space on the surface of the triangle (or if you prefer, ‘2-simplex’) is fair game (in other words, uniformly distributed). You could equally likely end up with a sample favoring only one topic, a sample that gives an even mixture of all the topics, or something in between.

For alpha values greater than one, the samples start to congregate in the center of the triangle. This means that as alpha gets bigger, your samples will more likely be uniform — that is, represent an even mixture of all the topics.

The GIF demonstrates the sampling of topic mixtures for the documents, but the Dirichlet distribution is also assumed the source (the Bayesian prior) for the mixture of parts per topic.

Three topics were used, as that works well when plotting in three dimensions. But typically, it is better to use more than three topics, depending on the number of documents you have.

If you look at the LDA tool mentioned earlier, you’ll see an alpha and beta slider.

These two hyperparameters are required by LDA. The alpha controls the mixture of topics for any given document. Turn it down, and the documents will likely have less of a mixture of topics. Turn it up, and the documents will likely have more of a mixture of topics.

The beta hyperparameter controls the distribution of words per topic. Turn it down, and the topics will likely have less words. Turn it up, and the topics will likely have more words.

Ideally, we want our composites to be made up of only a few topics and our parts to belong to only some of the topics. With this in mind, alpha and beta are typically set below one.

Why use LDA?

If you view the number of topics as a number of clusters and the probabilities as the proportion of cluster membership, then using LDA is a way of soft-clustering your composites and parts.

Contrast this with say, k-means, where each entity can only belong to one cluster (hard-clustering). LDA allows for ‘fuzzy’ memberships. This provides a more nuanced way of recommending similar items, finding duplicates, or discovering user profiles/personas.

You could analyze every GitHub repository’s topics/tags and infer themes like native desktop client, back-end web service, single-paged app, or flappy bird clone.

If you choose the number of topics to be less than the documents, using LDA is a way of reducing the dimensionality (the number of rows and columns) of the original composite versus part data set.

With the documents now mapped to a lower dimensional latent/hidden topic/category space, you can now apply other machine learning algorithms which will benefit from the smaller number of dimensions. For example, you could run your documents through LDA, and then hard-cluster them using DBSCAN.

Of course, the main reason you’d use LDA is to uncover the themes lurking in your data. By using LDA on pizza orders, you might infer pizza topping themes like ‘spicy’, ‘salty’, ‘savory’, and ‘sweet’.

You could analyze every GitHub repository’s topics/tags, and infer themes like ‘native desktop client’, ‘back-end web service’, ‘single paged app’, or ‘flappy bird clone’.

How does LDA work?

There are a few ways of implementing LDA. Still, like most — if not all — machine learning algorithms, it comes down to estimating one or more parameters.

For LDA, those parameters are phi and theta (although sometimes they’re called something else). Phi is the ‘parts-versus-topics’ matrix, and theta is the ‘composites-versus-topics’ matrix.

To learn how it works, let’s walk through a concrete example.

The documents and emojis are shown in the image above.

Our hyperparameters are:

• alpha = 0.5
• beta = 0.01
• ‘topics’ = 2
• ‘iterations’ = 1.

The following manual run-through is based on the academic paper ‘Probabilistic Topic Models’ by Steyvers & Griffiths.

Instead of estimating phi and theta directly, we will estimate the topic assignments for each of the four emoji using the Gibbs sampling algorithm. Once we have the estimated topic assignments, we can then estimate phi and theta.

To start, we need to randomly assign a topic to each emoji. Using a fair coin (sampling from a uniform distribution), we randomly assign to the first cat emoji ‘Topic 0’, the second cat ‘Topic 1’, the first dog emoji ‘Topic 1’, and the second dog ‘Topic 0’.

|         | Cat 0 | Cat 1 | Dog 0 | Dog 1 |
|---------|-------|-------|-------|-------|
| Topic 0 | *     |       |       | *     |
| Topic 1 |       | *     | *     |       |

This is our current topic assignment per each emoji.

|     | Topic 0 | Topic 1 |
|-----|---------|---------|
| Cat | 1       | 1       |
| Dog | 1       | 1       |

This is our current emoji versus topic counts.

|            | Topic 0 | Topic 1 |
|------------|---------|---------|
| Document 0 | 1       | 1       |
| Document 1 | 1       | 1       |

This our current document versus topic counts.

Now we need to update the topic assignment for the first cat. We subtract one from the emoji versus topic counts for Cat 0, subtract one from the document versus topic counts for Cat 0, calculate the probability of Topic 0 and 1 for Cat 0, flip a biased coin (sample from a categorical distribution), and then update the assignment and counts.

t0 =
(
  (cat emoji with Topic 0 + beta)
  /
  (emoji with Topic 0 + unique emoji * beta)
)
*
(
  (emoji in Document 0 with Topic 0 + alpha)
  /
  (emoji in Document 0 with a topic + number of topics * alpha)
) =
(
  (0 + 0.01)
  /
  (1 + 2 * 0.01)
)
*
(
  (0 + 0.5)
  /
  (1 + 2 * 0.5)
) = 0.0024509803921568627

t1 = ((1 + 0.01) / (2 + 2 * 0.01)) * ((1 + 0.5) / (1 + 2 * 0.5))
   = 0.375

p(Cat 0 = Topic 0 | *) = t0 / (t0 + t1) = 0.006493506493506494
p(Cat 0 = Topic 1 | *) = t1 / (t0 + t1) = 0.9935064935064936

After flipping the biased coin, we surprisingly get the same Topic 0 for Cat 0 so our tables before updating Cat 0 remain the same.

Next we do for Cat 1 what we did for Cat 0. After the flipping the biased coin, we get Topic 0 so now our tables look like so.

|         | Cat 0 | Cat 1 | Dog 0 | Dog 1 |
|---------|-------|-------|-------|-------|
| Topic 0 | *     | *     |       | *     |
| Topic 1 |       |       | *     |       |

This is our current topic assignment per each emoji.

|     | Topic 0 | Topic 1 |
|-----|---------|---------|
| Cat | 2       | 0       |
| Dog | 1       | 1       |

This is our current emoji versus topic counts.

|            | Topic 0 | Topic 1 |
|------------|---------|---------|
| Document 0 | 2       | 0       |
| Document 1 | 1       | 1       |

This our current document versus topic counts.

What we did for the two cat emoji we now do for the dog emoji. After flipping the biased coins, we end up assigning Topic 1 to Dog 0 and Topic 1 to Dog 1.

|         | Cat 0 | Cat 1 | Dog 0 | Dog 1 |
|---------|-------|-------|-------|-------|
| Topic 0 | *     | *     |       |       |
| Topic 1 |       |       | *     | *     |

This is our current topic assignment per each emoji.

|     | Topic 0 | Topic 1 |
|-----|---------|---------|
| Cat | 2       | 0       |
| Dog | 0       | 2       |

This is our current emoji versus topic counts.

|            | Topic 0 | Topic 1 |
|------------|---------|---------|
| Document 0 | 2       | 0       |
| Document 1 | 0       | 2       |

This our current document versus topic counts.

Since we’ve completed one iteration, we are now done with the Gibbs sampling algorithm and we have our topic assignment estimates.

To estimate phi, we use the following equation for each row-column cell in the ‘emoji-versus-topic’ count matrix.

Phi row column =
  (emoji row with topic column + beta)
  /
  (all emoji with topic column + unique emoji * beta)

And for estimating theta, we use the following equation for each row-column cell in the document versus topic count matrix.

Theta row column =
  (emoji in document row with topic column + alpha)
  /
  (emoji in document row + number of topics * alpha)

At long last we are done. The image above contains the estimated phi and theta parameters of our probabilistic topic model.

The matrix on the left shows us that the cat emoji is much, much more likely to represent Topic 0 than Topic 1, and that the dog emoji is much more likely to represent Topic 1 than Topic 0.

The matrix on the right shows us that Document 0 is more likely to be about Topic 0 than Topic 1, and that Document 1 is more likely to be about Topic 1.

This is how LDA can be used to classify documents (composites) and words/n-grams (parts) into topics.

If you enjoyed this article, you might also like Boost your skills, how to easily write K-Means, k-Nearest Neighbors from Scratch, and Let’s make a Linear Regression Calculator with PureScript.

How have you used LDA? Do you prefer Gensim or MALLET? How cool would it be if Elasticsearch did topic modeling out of the box? Let me know in the responses below. Thanks!

There comes a time in most every app’s life when it needs distribution. If you can, it’s best to ship it in as many ways as possible. Still, if you’re targeting Ubuntu—or Linux in general — a decent solution is to create a snap.

What is a snap?

According to the Snapcraft website, “Snaps are universal Linux packages.” The end user goal is to provide a no-hassle way to download software and keep it up to date as new revisions come out. No building, compiling, transpiling, linking, making, make installing, and/or dependency downloading — just download the snap and you’re off to the races.

So how do I get started snapping my app?

I recommend firing up a virtual machine running Ubuntu 16.04 even if you use Ubuntu as your daily driver. This will give you a clean slate and you’ll have the most documentation/support at your disposal.

Before we continue, I’ll make this concrete by going over what it took to snap Movie Monad — a mildly-popular Haskell app. For another example, checkout Gifcurry, a great Haskell app that converts videos to GIFs.

With the virtual machine up, you’ll need to install snapcraft and everything needed to run its cleanbuild command. You could do away with the clean build approach but this will help you work out the kinks faster and keep your build nice and well…clean. I once failed the linting process because a stray Vim .swp file found its way into the final squashFS file system.

mkdir -p ~/my-snap-builds/my-app/snap/gui
sudo apt install snapcraft lxd lxd-client
sudo usermod -a -G lxd myusername
sudo lxd init
cd ~/my-snap-builds/my-app
snapcraft init

If everything went to plan, you should end up with a directory structure like this.

~/
  my-snap-builds/
    my-app/
      snap/
        gui/
        snapcraft.yaml

If it is a GUI app, you’ll want to place a .desktop file and icon under gui/.

How do I fill out the snapcraft.yaml file?

The first entries of the file are the metadata for use in the snap store. I recommend a snappy summary since this is all they’ll have to go on when searching the snap store.

snap search movie-monad
# Name         Version  Developer  Notes  Summary
# movie-monad  0.0.4.0  lettier    -      A free and simple to use video player built with Haskell.

The grade must be stable to release the snap into the stable channel. Once you figure out what permissions or “plugs” your app will need, make sure to set the confinement to strict.

After the metadata, there are two major sections — the apps and the parts. For Movie Monad, there’s only one app. The command subsection contains a “desktop launcher” which is a convenience wrapper provided by the Snapcraft team. If your app is GTK or QT based, be sure to look into it.

The Movie Monad snapcraft.yaml file has two major parts. There is the Movie Monad build/install part and the desktop-gtk3 part which sets up the GTK+ desktop environment. The Snapcraft team provides the desktop-gtk3 part. I list it under after informing the Snapcraft build system to create that part after the Movie Monad part.

If your app has a standard build and install process (./configure, make, make install) then you can use a plugin. I’ve deviated from the norm, so instead of a plugin, I created my own scriplets.

Scriptlets are shell scripts sourced directly from your snapcraft.yaml, to change the behaviour of a plugin. — https://docs.snapcraft.io/build-snaps/scriptlets

The most elaborate scriptlet is the install one. In this scriplet, I take the output files from cabal and move them all over to the install directory. It is the install directory that the Snapcraft build system will squash into a snap file.

Backing up a bit, you’ll see a list of build-packages and stage-packages. The build packages are the software you’ll need to build your app’s executable file(s). The stage packages are more than likely the run-time dependencies your app needs. The build packages do not make it into the final snap file — so if you only need it to build — do not list it under stage packages.

Movie Monad uses the Haskell Stack build tool to make the build process as reproducible as possible. Unfortunately, the resulting executable is not all that relocatable or portable. Portable meaning you can move the build directory around and the app will still run. Snapcraft recommends that your app be relocatable.

The main concept to snap your software is that your application needs to be relocatable. It’s a good practice to not rely on hard coded paths like /etc and such, but to read your assets, configuration, hooks from subdirectories of your application. — https://docs.snapcraft.io/snaps/philosophy

Having the build be portable is important since Movie Monad relies on data files at run time. So to have both a reproducible and relocatable build, Movie Monad uses both Stack and Cabal. After the build scriptlet finishes, the .cabal-sandbox directory is created and its contents are relocated into the install scriptlet.

With your snapcraft.yaml file done, run the clean build command.

cd ~/my-snap-builds/my-app
snapcraft cleanbuild
ls
# my-app_version_arch.snap my-app_version_source.tar.bz2 snap/

How do I get my snap into the snap store?

With your snap built, you’ll need to setup an account if you haven’t already.

cd ~/my-snap-builds/my-app
snapcraft login
snap login myusername@myemailprovider.com
snapcraft register my-app
snapcraft push my-app_version_arch.snap
snapcraft release my-app 1 stable

And with that, you’ve snapped your awesome Haskell app!

What snags, if any, did you run into?

The snapping process came together well. I did run into a bug with the Snapcraft site when trying to undo a revoked name. I had deleted my yet unreleased snap which locked me out of the name — don’t do that. The moderator noise, from the forums, was very helpful and recovered the name for me.

The snap itself does have some issues that are not present in a regular build of Movie Monad. If you run the executable out of the sandbox, all the issues go away. Based on this, the sandboxing has some issues that need work.

Where can I find more information about Snapcraft?

For more information head over to the Snapcraft site and be sure to make a stop at the forums. The community there is very helpful.

How do you use snap? What apps have you snapped? Do you like Flatpak, Snapcraft, or AppImage better? What Haskell apps do you enjoy? Let me know in the responses below. Thanks!

Found in a list of 100+ interesting data sets, the Texas Department of Criminal Justice provides different collections of information on death row inmates both present and past. Prior occupations for each current offender are listed here.

Dependencies

We’ll need some packages to scrape, cluster, and chart our findings.

• rvest: “Wrappers around the ‘xml2’ and ‘httr’ packages to make it easy to download, then manipulate, HTML and XML.”
• wordcloud: “Pretty word clouds.”
• tm: “A framework for text mining applications within R.”
• apcluster: “The ‘apcluster’ package implements Frey’s and Dueck’s Affinity Propagation clustering in R.”

Collection

The data we wish to look at is not in the form we need it. We’ll need to capture the HTML and parse it looking for the prior occupation information. Using rvest, we will grep for all <p> tags that contain the occupation information. Not every page is consistent so we will need some logic to hunt around for the prior occupation field. Once we’ve parsed every page, all of the raw information will be saved to a CSV file for later pre-processing. Each line corresponds to each death row inmate prior occupations collected.

Pre-processing

With the CSV file opened, we need to clean each entry for unwanted white-space and punctuation. For those with multiple prior occupations, we’ll split on the commas. Once cleaned, we’ll add each prior occupation per inmate to the inmates_occupations list.

Looking over the dataset, you’ll notice some redundancies such as mechanic versus auto mechanic. With care, we will condense the prior occupations to the sub-strings of the redundancies. We’ll also need to hard-code some corrections for irregularities such as fork lift versus forklift. Once the duplicates have been merged, we’ll generate a unique list of the prior occupations for our axis labels.

Mining

We have collected, cleaned, and removed erroneous variations in our dataset. Now we’ll move on to mining and plotting/charting our data.

Total Prior Occupation Relative Frequency Distribution

Let us begin by charting the relative frequency of prior occupations listed across all sampled inmates.

The unique prior occupations are in alphabetical order along the x-axis. The y-axis is the relative frequency distribution. laborer accounts for nearly 41% of the 291 listed prior occupations among the 182 death row inmates sampled. Attributing to its large percentage was the merging of duplicates, for example, general laborer and assembly line laborer into just laborer. One could argue that they are distinct labels. construction and none are the second and third largest respectively.

We can explore the dataset further by clustering the sampled inmates by the prior occupations they had. We’ll treat each inmate as a document with their prior occupations making up the document. By clustering the inmates via their prior occupations, we can partition the dataset into different prior occupation profiles.

Inmate Prior Occupations Matrix

To begin clustering, we will need to vectorize each inmates’ prior occupations. We’ll assemble these vectors, into the inmate_matrix_count where [i][j] is >= 1 if the i-th inmate had the j-th occupation and zero otherwise. No inmate had the same prior occupation listed more than once, so no count will be greater than one.

Prior Occupation Weighting (TF-IDF)

Since we are dealing with text and that nearly half of all sampled inmates were a laborer at some point, we’ll perform a term weighting technique known as TF-IDF. Given that an inmate was both a laborer and welder at some point, TF-IDF will weight laborer less since welder appears less frequently in the text corpus. Knowing that an inmate was a laborer does not say as much as knowing they were also a welder.

Multidimensional Scaling (MDS)

To visualize the inmate vectors in two dimensions we’ll employ multidimensional scaling.

An MDS algorithm aims to place each object in N-dimensional space such that the between-object distances are preserved as well as possible. — Multidimensional Scaling, Wikipedia, the free encyclopedia

We can see a large mass around the origin. Another distinct mass is seen at (-0.8951273 -0.702121).

Affinity Propagation (AP) Clustering

Due to the concave shapes and variable density of the MDS scatter plot, we’ll employ Affinity Propagation Clustering. This has the added benefit of not having to specify the amount of clusters ahead of time (K).

With the inmate_matrix_tfidf_mds clustered, we can now plot the clusters.

In total, the algorithm generated 17 clusters. Cluster membership sizes range from one to 92 inmates.

Inmate Clusters, Prior Occupations Relative Frequency Distributions

Now let us generate a relative frequency distribution bar-chart for each TF-IDF MDS AP cluster.

Cluster 1, seen at (-0.8951273 -0.702121), is solely comprised of none which agrees with the dataset. Intuitively, if an inmate had no prior occupations, you wouldn’t expect to see other prior occupation terms clustered with none.

The following bar-charts are the clusters making up the large mass centered around the origin.

Cluster 5 accounts for the inmates that were mainly laborers with only a very few having one other prior occupation. This cluster also contains a large portion of the unique prior occupations found in the raw data set such as computer software.

For cluster 10, there is a large mixture of both laborer and warehouse.

Cluster 17 is more difficult to interpret and could have been likely clustered with cluster 5, however, it is the only cluster that accounts for the inmates that had unknown prior occupations. unknown did not collocate with any other prior occupation so it is surprising to find it clustered with other prior occupations. This is likely due to the MDS.

Automatic Cluster Labels

Using differential cluster labeling and more specifically pointwise mutual information (PMI), we can label each cluster according to its prior occupation with the highest association.

• Cluster 1: none
• Cluster 2: mechanic
• Cluster 3: mechanic
• Cluster 4: construction
• Cluster 5: laborer
• Cluster 6: cook
• Cluster 7: welder
• Cluster 8: welder
• Cluster 9: ac
• Cluster 10: warehouse
• Cluster 11: construction
• Cluster 12: clerk
• Cluster 13: shipping
• Cluster 14: clerk
• Cluster 15: welder
• Cluster 16: mechanic
• Cluster 17: unknown

Condensing these even further:

1. none: cluster 1
2. mechanic: cluster 2, 3, 16
3. construction: cluster 4, 11
4. laborer: cluster 5
5. cook: cluster 6
6. welder: cluster 7, 8, 15
7. ac: cluster 9
8. warehouse: cluster 10
9. clerk: cluster 12, 14
10. shipping: cluster 13
11. unknown: cluster 17

This effectively condenses down the original 60 prior occupations down to the 11 most prominent in the sampled data. These 11 prior occupations could all be described as blue-collar occupations with the exception of clerk.

TF-IDF AP Clustering Only

Comparing the TF-IDF MDS AP clusters to TF-IDF AP clusters, using only the inmate_matrix_tfidf, the Affinity Propagation clustering algorithm generated 48 clusters using the original 60 dimensions versus the 17 clusters generated using the two dimensions found by MDS.

These 48 clusters are more granular with a clearer partitioning of inmates with unique prior occupations. 30 out of the 48 clusters contain only one inmate due to their unique combination of prior occupations. Cluster membership ranges from one to 71. Like with the MDS clusters, none is its own cluster. However, unlike the MDS clusters, all of the unknown prior occupations are clustered together alone.

Latent Semantic Indexing (LSI), Singular Value Decomposition (SVD)

We can take the TF-IDF normalized inmate-prior-occupation matrix and perform SVD on it.

LSI can be viewed as soft clustering by interpreting each dimension of the reduced space as a cluster and the value that a document has on that dimension as its fractional membership in that cluster. — Introduction to Information Retrieval

This will give us three matrices U, D, and V. U contains our inmate-concept vectors in the new orthogonal basis.

We’ll need to choose a K <= R (R being the rank) where R=60. At K=38, 90% of the variability of the original matrix is explained.

Now let us cluster and plot the prior occupation relative frequency distribution for each resulting cluster.

After clustering, 40 clusters were found. Contrast this with the 48 found by TF-IDF alone which used 60 features instead the 38 used after applying SVD. Cluster membership ranges from one to 71.

Below are the cluster labels found by PMI:

• Cluster 1: computer operator
• Cluster 2: none
• Cluster 3: kitchen worker
• Cluster 4: computer programmer
• Cluster 5: construction
• Cluster 6: warehouse
• Cluster 7: landscaper
• Cluster 8: cabinet maker
• Cluster 9: sales
• Cluster 10: pipe fitter
• Cluster 11: laborer
• Cluster 12: barber
• Cluster 13: machine operator
• Cluster 14: truck driver
• Cluster 15: oil field
• Cluster 16: food service
• Cluster 17: roofer
• Cluster 18: fabricator
• Cluster 19: cook
• Cluster 20: computer technician
• Cluster 21: janitor
• Cluster 22: wrecker driver
• Cluster 23: painter
• Cluster 24: hydro-water blaster
• Cluster 25: ranch hand
• Cluster 26: heavy equipment operator
• Cluster 27: iron worker
• Cluster 28: shipping
• Cluster 29: computer software
• Cluster 30: clerk
• Cluster 31: plumber’s helper
• Cluster 32: welder
• Cluster 33: mechanic
• Cluster 34: carpenter
• Cluster 35: forklift
• Cluster 36: heating
• Cluster 37: unkown
• Cluster 38: food service
• Cluster 39: jewelry designer
• Cluster 40: ac

Wrap-up

We collected, parsed, and mined the prior occupations of current death row inmates. Interesting patterns discovered were the large portion of blue-collar occupations (most notably laborer) and more rare prior occupations such as computer operator and jewelry designer. An interesting hypothesis test would be the correlation between being on death row and having been a laborer. The SVD computation could be used for information retrieval allowing one to search for similar current inmates by some prior occupation query. Further analysis could include plotting the amount of each prior occupation seen per year.

Appendix

Full SVD AP Clustering

Full Source Code

Originally published at lettier.github.io on February 17, 2016.

Find more at Lettier, Blog, Twitter, Github, and LinkedIn.