In the previous Lambda Fu Powerup, I discussed Spectra, a functional graphics framework I’ve been working on, using Swift and Metal. In this entry, I’m going to discuss some specific techniques I’ve learned with functiona programming, beyond the basic boring “Look at my glorious monads” post. There’s so much info out there on introductory functional programming using category theory, but there are very few posts I’ve seen that delve into higher-level design concepts that build on monads, bind, etc. At least, there aren’t very many that are written in a language besides Haskell, which is pretty dense for someone who hasn’t much experience with it. Haskell intrigues me and it’s near the top of my list for the next language for me to learn, but I just don’t have the time right now.
Optics: Lenses and Prisms
The answer to my problem has been optics, which is a pattern borrowed from Haskell that enables you to zoom down into object like structures, functionally, with lenses and prisms. You can retrieve data several layers deep by composing them together and also compose their setters. I’m going to assume that you’re familiar with the basics though because there’s a lot of good content out there for this. I’ll link to it at the end of the article. I really think that lenses are a great example of one of those higher-level design patterns for functional programming that enable you to see what it’s realllly all about.
First, I’m going to tackle some high level concepts about why lenses would be useful. Some people just can’t see it. I saw some pretty ugly comments on this lightning talk on lenses and prisms, where some people obviously just didn’t get it. And i’m not gonna lie, it’s not easy to figure out. Some libraries are more basic than others and you’re going to want to use lenses that allow you to return objects of various type and arity because that allows you to return a tuple containing your target and functions for callback or continuation (i.e. retaining references for deferred execution). This is an important point though because there are a few of libraries out there that don’t give you the full Lens<S,T,A,B>, which allows you to be more fluid with how you work with these objects.
If you can’t return a different tuple for the modified source or the modified target, that means you can’t return deferred functions for callback or continuation.
By the way, if you’re using swift,
Typelift/Focus is a fantastic
implementation of lenses. It’s broken down to be completely
functional and based on the
IxStore monad. It also includes the
IxCont monads, each of which has
several traditional operators implemented, like
Note: if you don’t understand what
IxCont actually do in
Typelift/Focus, then you don’t
understand how to use this library and you likely don’t understand
how to use lenses. If you’re coming into this just by using Focus to
create lenses and prisms with getters and setters, you’re missing the
point because that doesn’t give you anything that object oriented
You need to trace through the source from the Lens
IxState implementation. After doing so, with some
reflection, I finally “got it” and I could finally say that I
understood functional programming beyond monads and simple
categories. I still have a ton to learn, but that’s why I feel that
learning about lenses is worthwhile for someone that’s interested in
upping their ** Lambda Fu **.
So, I’m doing you a huge favor by writing this article. No, it won’t include lots of code snippets. In the past, for me, looking at tons of Haskell and F# code snippets basically did nothing for me. Writing Haskell and F# code may have allowed me to get it, but I don’t have much experience with those languages. Talking to the right people may have allowed me to grasp it, but I don’t know very many people in my area who are interested in truly functional code.
I’m doing you a huge favor because I’m summarizing some functional programming techniques, which for me were very difficult to identify on my own. For example, I’ll describe how to process elements of a tree or list in order to collect continuation monads to be executed later. When I review my first functional approach to transforming XML node trees later, I’ll explain how continuation monads were really the missing piece.
Parameterized Types for Lenses
S => Source
T => Modified Source
A => Target
B => Modified Target
Read over that real quick. It’s a bit confusing, but that’s OK. T
isn’t the Target type. If you’re like me, you’ll trip up on that a
few times. A Lens is composed of a getter and setter. The
a morphism from
S => A and the
(S,B) => T. However,
a complete get/set operation on a Lens is a basically morphism from
=> T. With the getter, you extract from source
S some target type
A into a context where you can modify it to type
outside the lens, unless using
It Zøøms Ze Thingz
Sounds pretty simple, right? Here’s where things get interesting. You
can also use the
zoom<X> method from to inject affect the arity of
data returned from a Lens Getter. That is, you can use
return not only the object you’re inspecting, but also some
information about it or some monad to call later. In order to use
zoom, you’ll need to understand
IxState, which is a state monad
implementation. However, you’re basically just zooming into the lens’s
context and passing the
IxState down to it. This returns another
IxState coupled to the lens’s getter context and the
essentially a monad that transforms the lens getter into type
(X, A) where
X is whatever type you passed in with the
But what does it alllll meannn?!
What all this means is that not only can you retrieve whatever
Target type you normally retrieve with your lens, but you can also
perform some transformation using other elements available in the
closure of the
IxState monad you passed in to return a tuple of type
(X, A). Here
X could represent some kind of
state or an
coupled to transition behaviors for a state machine or simply a map of
collected callback behaviors. In other words, whereas the lenses
typically process object-like data container types, the
method allows you to specify any type
X that acts as monadic glue.
So, if on one of my XML nodes, I define a property that tells my
generator that I should always register this to a dependency injection
container, but only after
generate() has completed processing all
nodes, then I can use
zoom<X> to return a callback with the
generated node. I would then collect the callbacks into an array as
I’m processing the list/tree of nodes to generate. And because the
closure for D/I registration was created within the
it’s still coupled to the reference to the node and maintains that
until it’s called later. This is somewhat useful with one type of
callback, but moreso useful when you want to collect multiple types of
callbacks when processing a tree or list.
zoom<X> and a few other Optics techniques allow you to
create an interface between object-like structures that hook them
together with a kind of functional state-machine glue. AFAIK, I am
still a novice here, but that’s what it seems like to me. It’s a kind
computational metatype or something. Over the past few days, I’ve
been thinking about whether there would be generalized
λ-glue objects and, if so, what they’d look like. I’ve also
been thinking a lot about how the typical functional operators
imap would apply to lenses and prisms. It’s easy to see
what these do, but it’s a bit harder to understand how to apply them
towards design without having a ton of experience.
Other Incredibly Useful Techniques with Optics
The two main optics types are
Prisms. I’ve covered
Lenses pretty thoroughly and these work great for for processing and
Product Types – tuples and structs. Prisms work far
better for processing
Sum Types, which are enums for Swift. Sum
types are also referred to as
disjoint unions. So with prisms, you
can instantiate an enum type or evoke various transitions from them to
another. And your getter produces an optional for the target, so your
A => B can handle the case where
S => A? returned a
As for the
IxStore<O,I,A>, these are mainly a means to store context
(i.e. closure) for
Prism. When you create a
Typelift/Focus does under the hood is create a function
that returns an
IxStore<A,B,T>. This store is indexed by a value of
type A, the target returned by the lens getter. When you run
peek on the the Store, you’re accessing a coherent context for the
setter monad you created the lens with.
One thing that looks interesting for
IxStore is “braiding” together
IxStore objects returned for lenses and prisms with
seeks. I haven’t done any of this
yet and since it requires 4 for 5 generics, so keep that in mind. But
it may be very useful to do so, since you’re recomposing lenses in a
more general sense than with just compose.
Here It Is Y’all: the Hokey Pokey
And that’s what functional programming is all about: taking these small units of behavior and recomposing them as you need them. And to do so, you have to construct your programs such that these pieces retain the ability to be recomposed. The smallest pieces are the best, but the tradeoff is that it requires a ton of glue to recompose them in pursuit of a program that is actually useful.
I’m in search of a general technique for combinatoric deconstruction of code & design patterns into small chunks of functionality which can be algebraically reconstructed. The issue is the same with functional programming & category theory: and that is everything is so general that it’s difficult to relate the tools of functional programming to the actual, concrete application of any problem.
IxStore x Dynamic Programming
Another useful technique for IxStore would be an IxStore that memoizes
the results of retrieval and update operations for dynamic
programming. But it would only be useful in circumstances where you
B => T to be deterministic. There are similar
performance optimizations and dynamic programming techniques when
you can guarentee that
S => A is also deterministic. In this
case, you can cache the monadic
IxStore objects that that are
returned by the lens getter, and thus, the stores closure and
execution path can be predetermined. However, many of these
operations are so fast anyways that you don’t really save any time
by doing this. In general functional progamming is excellent at
enabling the developer to silently inject behavior to be utilized
for dynamic programming or to otherwise alter behavior. Dynamic
programming techniques are only useful when you’re given sufficient
Again, there are some optics libraries out there which don’t provide
the four parameterized types for lenses.
SimplePrism are examples of these in
Typelift/Focus and they’re
useful for some situations I’m sure, but they lack the capacity to
provide most of what makes these optics so useful in functional
programming. Without the full range of type parameters for optics,
you can’t process your
AltTarget type to be stored in
AltSource type that differs from
That is, your morphisms on
Target are restrained to
automorphisms. That means
AltSource can’t be a tuple of
(Source, (Something -> Else)), which restricts the capacity for
continuations. Similarly, you can’t modify
Target and then specify
a tuple of
(Target, (Something -> Else)) as the
AltTarget type for
your setter. If you can do this, then you can trigger alternate
behavior that’s coded inside your
Setter. Maybe you want your
setter to include conditional behavior triggered by it’s parameters.
Or maybe you want your setter to execute an optional monad that’s
included with the parameters.
You can’t do the above, if you’re restricted to
Source == AltSource
Target == AltTarget. But, if you haven’t done a lot of
functional programming in the past, you might have a hard time seeing
why this is restrictive. At least, at first. I did.
Again, it’s hard to adequitely summarize the utility offered by the
Zoom<X> method in
Typelift/Focus. It’s so useful, especially with
IxCont and that computation metatype concept I just mentioned, which
seem like great ways to recursively process trees like parsed XML
docs. Another design pattern that seems incredibly useful is using
Lens.fanout(). Doing so with
multiple lenses operating over similar Source & Target types could
allow you to evaluate the result of multiple similar operations. This
is basically like a kind of “horizontal composition.” This horizontal
composition can also be usef to simultaneously retrieve both a
property and a pair it with the right monad to be continued.
“Continue. Continue. Continue… Continue.” - Dr. Pavel Pezner
IxState essentially allow you to do is
construct these discretized trees of indexable operations. These
functional trees are malleable via functional programming operators
and optics that allow you to braid operations together and specify how
you can insert new behavior into the branches of the tree at specific
points. That’s like a 10,000ft view that summarizes what I’ve learned.
Optical Lambda Trees
I’m really just making this shit up. There is no such “thing” as an optical lambda tree, but I’m not sure what to call this. For processing or transforming tree-like or graph-like data, there is an inverted tree-like structure composed of either maps or tuples. In the case of tuples, the first entry is the next lens to cap on, required for each of tis operations. The next entry is a self-similar data structure describing subsequent levels of processing. For maps, the keys are either values or lenses. If the key is a value, then no recursion is necessary and the value attributed to that key is processed with the lens stack. If the key is instead another lens, it is composed onto the current stack when processing the data attached to that lens key.
And for this Optical Lambda Tree – or whatever you want to call it; I’m sure there’s a better, more descriptive, more technical name… Anyways, for this tree, there is an associated recursive function, or dictionary with several defined & recursive behaviors, that processes the tree of data using the “lens-tree” to provide instructions and data access logic. Such a functional can also be used to simultaneous iterate through the tree and collect data or functional units of behavior to be applied later, as continuation monads.
All in all, for a specific example relating to graphics, this technique could be used to transform/update branches of a tree, while storing information about which parts of a tree need to be registered for dependency injection or be instantiated with buffer allocation after initial processing is complete. That is a great example of how to use this to process the tree of nodes for a Scene Graph.
It’s still complicated as hell though. But so is any solution to the efficient distribution of computing resources in a scene graph of objects to be rendered. It is very difficult to find a simple way to distribute resources for rendering, while providing flexibility and limiting complexity. There are so many interdependent constraints.
A quick fable on the seductive promise of “unified” frameworks
Usually frameworks that promise to simplify the deployment of a mobile app to multiple frameworks actually increase complexity. Instead of the implementation details being a result of the complexity of the union of those two frameworks, it’s more like the complexity of one of these frameworks is like the product of the disparity of those two frameworks. Frameworks built on Cordova, like Ionic, can be useful though, but you’ll find yourself running into a ton of problems.
Moral of the Story
These unnecessary abstractions never actually simplify anything. A solution that maps multiple problem spaces into one usually needs to take into account all the complexities in each one. Therefore, you have to make a choice between flexibility and excessive configuration or simplicity and convention. But in neither case do you have a simplified problem space.
And so now you have FOUR problems: you need to learn the API for iOS, the API for Android, the differences between them AND the API for Ionic. Or whatever framework (not trying to pick on ionic here)
For Cordova-based frameworks, you’ll find that many of the plugins only have one implementation. Or that the API/design of the problem domain addressed by a plugin diverges so significantly that there is no single API that could reasonably simplify it.
Parsing XML with Swift
So now for a few, quick examples. I just want to explore an alternative to lenses. This is the functional technique that I wanted to explore first, before I discovered lenses.
First of all, there are a lot of Apple developers that will be quick to ask why I chose XML over PLists, since those would have been much easier. Yes, yes that was most certainly a mistake. However, I’d still have the problem managing the parsed trees of data, regardless of whether I’d used XML, JSON or PList.
And why would I spend so much time on this? I was really searching for a means of retaining functionality while ensuring my interface for working with pipelines and the scene graph would be uniform, instead of complicated and highly variadic. That’s another thing that’s magical about functional programming – uniform interfaces. Fucking pixie dust. I love it. I tried several things to achieve this end. I thought I could pass in a closure, along with metadata for the tree of nodes I was generating, but this didn’t resolve the complexity. It was like a shell game where I was shifting the complexity from the interface to the implementation.
While I found this to be a very useful pattern, actually implementing it to override how XML nodes were generated into Model I/O objects was clunky in real practice. If one needed to replace a mesh that was three levels deep in an XML node tree, it meant a developer would have to mostly hand code a structure that mirrored the node tree down three levels at least. That is, it’d actually be simpler just to instantiate the classes by hand than to ever use the XML at all, if you wanted custom behavior by composing subtrees of XML nodes together. I eventually found that lenses and prisms were the functional answer to this problem.
The SpectraInjected Tuple
The MetalNodeInjector Closure
The MetalNode Protocol
So, basically what I was trying to provide with this interface was a means of expressing the differences between a parsed node tree and the node tree that you want to generate. For example, you might parse an XML for an object to render representing a general type of enemy or something. But say you want to reparse it and render one section with a different color. Or apply a different texture to some meshes that are located two or three levels into the mesh. But you still want to share 99% of the resources for the object. That is, the data for the triangles in the meshes, you don’t want to allocate that memory that twice if you don’t have to. That’s expensive in terms of time and memory!
So, I wanted to find an answer to this so that it was simple and efficient. It’s still going to be complicated, but I think that Lenses and Prisms will help me delve in to a node tree, swap out the things that are different, while still allowing me to share memory resources.
Yet people want to act like I can’t parse XML or some shit. Excuse me for not having someone I can ask that just gives me the answers. That’d sure be nice.
So to mi, lenses have been so crucial to understanding the deeper mysteries in functional programming. They were really the first example of a ‘higher-order’ functional programming structure or design pattern that I understood. I say higher-order, since I am well acquanted with things like monads, compose and bind. But, while fairly straightforward to understand, monad or compose or bind – these are just general concepts.
For me, the challenge is not how, it is why. It’s not how do I use these tools, but where should these tools be used to acheive a design? And how does one envisage the overall design? And this abstract non-sense really is the boon and curse of functional programming. It’s so generalized that it can apply to anything. But again, it’s so generalized that it’s difficult to attach to things in some concrete way.
Here’s some resources that I’ve found to be invaluable in learning functional programming techniques.
First of all, the F# for Fun and Profit blog is fantastic and so are Scott Wlashin’s videos. I’d recommend starting out with Functional Design Patterns and A Functional Approach to Domain Driven Design. Then, finally, take a look at Coding Like Frankenstein, which is a great story about Dr. Frankenfunctor and the Monadster. These videos talk about functional programming using F#, which is a strongly-typed language from Microsoft, very similar to Haskell in it’s capabilities and implementation. I wish I’d known how cool that was about 7 years ago lol.
I’m impressed, Microsoft.
If you’re looking for some Swift examples of functional programming and, in particular, presentations on optics, here’s some links. First of all, Brandon Williams has a lightning talk on Lenses in Swift using MST3K as an example. What an excellent choice! Brandon also has a blog on implementing a basis for algebraic structures in Swift like Magmas and Semigroups. I haven’t watched it yet and I don’t really know what those things are … but uhhh mag-ma!
Or… nevermind, I guess I was thinking about the implementation of Magma in Typelift/Algebra. Mr. Williams, where is the magma?
The best talk that I found in relating the usefulness of lenses was The Unreasonable Effectiveness of Lenses for Business Applications, which involves some Haskell, but not too much. I love Haskell, but it’s a bit dense for me to parse right now.
Lambda Fu #3
HOAS & PHOAS - Alien Haskell Technology
So, next time, I’m going to explore AST manipulation and Type Theory. AST’s are ridiculously useful, but incredibly complicated.
These infinitely valuable AST/HOAS/etc structures are to functional programming, it’s very difficult to see why these are more useful than they appear on the surface. Without context and a clear understanding of the mathematic notation, it’s hard for me to parse together how these objects can be used, though my imagination runs wild. It appears that these AST’s are indeed very difficult to work with, as the examples of programmatic manipulation seem limited and are described by the authors as such.
Here’s some articles that I’ll be reading over the next month or so. There is Type Safe Code Transformations in Haskell and Parametric Compositional Data Types, as well as some other papers with HOAS/PHOAS transformations of AST’s in Haskell.
And thats because the only language which seems to have a decent amount of examples of this stuff is haskell. That’s because it’s purely functional and many of these design patterns are only needed or applicable when working with a Strongly Typed functional language. Lisp implements a lot of similar stuff with macros, but it’s different, since one can more easily handle disparate types with dynamic types. Also, clojure’s destructuring is one of my favorite features of any programming language. this right here solves so many problems.
Another pattern I found to be immensely useful in my quest to process these tree-like data structures are the Extensible Records available in the Elm Programming Language.
That’s it for today. Peace!