Understanding Combinators

Learn
1

Hey friends,

Recently I’ve come across two great libraries that use combinators to build great abstractions:

As someone who isn’t very familiar with the concept of combinators, I’d like to gather and read resources on combinators to gain a deep understanding.

There’s a Medium post that specifically talks about tea-combine (link), but I’d like to see if there is a more general post / tutorial on using combinators that will help me grok this concept.

1 Like
2

First Reaction

My understanding is that the term “combinators” is not a topic on its own. It generally see it as a modifier term for existing things. So “X combinators” is generally like saying “X where I have thought about how to combine one X with another X pretty carefully.”

For example, a person who uses this term might say elm/parser is a library of “parser combinators”. Their meaning is “these are parsers that can be combined” and they may be using the term (1) just because other people say it or (2) to draw a contrast with parsing systems that may not have functions for fitting parsers together. So parsers like regex or lex/yacc would be distinct from “parser combinators” when talking about parsing techniques in a more formal setting. (In my experience!)

I think things that get this modifier added to them might often have map or map2 or andThen functions, but I do not think “combinator” has a consistently used technical meaning with regards to which of these functions are available (or if there is some other mechanism for combination!)

For example, the Arrowized FRP work here refers to “AFRP combinators” that are pretty different from the typical map2 or andThen approaches. In this case the meaning is roughly “AFRP functions for combining things”.

Better Definition

I think the term “combinators” is generally (always?) used for things embedded within an existing language, so perhaps it is distinguishing between “a language for X” vs “a set of functions for X”. I’m not thinking of counter-examples for this definition right now! Maybe that’s the best definition!

That said, I do not personally find this term super clarifying in casual usage. Maybe in research literature where some researchers make new languages (X) and other researchers make libraries embedded in existing languages (X combinators). Outside of that, it can make things seem more complex than they really are, having the effect of making things less clear and harder to understand. (It’s sort of redundant to say “X combinators” about a library anyway. The fact that it is a library already makes this distinction I think.)

That’s just my perspective on it though. Hope that helps!

9 Likes
3

There are two meanings of the word “combinator” in functional programming.

The first one, not that commonly used, is for a lambda function not depending on any outer variables (or free variables, as literate calls them). So \f x y -> f y x is a combinator, but \x y -> g y x is not, because it refers to the free variable g. More info on Wikipedia’s page on Combinatory logic.

The other one, as Evan already hints at, is a library about a type T (commands, tasks, parsers, forms, drawings, …) together with

  • functions to create basic values of type T,
  • and functions to combine these basic values of type T into new values of type T.

In case of composable forms you’re referring to, functions like custom, field, and succeed create values of type Form. Functions like append, andThen, optional etc. combine Forms into new Forms. Therefore it is called a combinator library.

5 Likes
4

Reading Raymond Smullyan’s To Mock a Mockingbird is a fun way to go about grokking combinators.

From the preface:

“You will learn some fascinating things about combinatory logic. … Despite the profundity of the subject, it is no more difficult to learn than high school algebra or geometry.

Combinatory logic is an abstract science dealing with objects called combinators. What their objects are need not be specified; the important thing is how they act upon each other. One is free to choose for one’s “combinators” anything one likes (for example, computer programs). Well, I have chosen birds for my combinators—motivated, no doubt, by the memory of the late Professor Haskell Curry, who was both a great combinatory logician and an avid bird-watcher. ”

5

I would like to add that nax/tea-combine seems problematic IMO - allow me to explain why, so you can decide if you (dis)agree:

“combinators” (I think of these as “functions for combining things abstractly”) are great when you have a set of things that needs a lot of combining. These functions incentivizes you to have a lot of these things to combine IMO.

The Elm Architecture is the underpinning of an Elm-application: I find it problematic that these modules encourage people to have multiple fragmented (or complete) Elm programs within a single program.

I don’t think this pattern should be encouraged.

I’d like to add that I’m a rational thinking person who is open to criticism, so let me know if you have another point of view that might inform me of something I’m missing, misinterpreting, or misrepresenting :sunny:

2 Likes
6

Out of curiosity, what do you think people should use instead when the level of complexity of a single section of a page exceeds the level of complexity of multiple pages put together from the available architecture examples?

If you need to visualize an example, think about the level of complexity of TodoMVC but with http calls attached to each UI interaction. Then think that there are about 6 of those sections on a single page. What do you do then?

This topic is a sensitive topic in the Elm community.
As far as I’ve seen, it was framed in dichotomic terms of either keeping everything flat and pure OR succumbing to the “disaster” of objects. The trouble is that this strategy has failed. The discussions did not stop and people keep bringing it up. From what I’ve seen, this is related to the inherent complexity of the topic. It might have seen like a beginner issue (“folks coming from React”) when it started but the trouble is that I’ve been working with Elm in production for 3 years with no prior React knowledge and I have not found a comfortable solution to the problem.

I have a file in one of my projects that handles a single page. It is a 2.6k LOC monstrosity that screams for refactoring. With this file I tried my best to follow the flat model mantra. Almost all view code is away in some other modules, all http calls are away in an API module. The main type of that page is in its own 1k LOC module together with decoder/encoder and all the helper functions that do various validations and data transformations/extractions. Some of the widgets used on this page live in their own module with their own Model/update/view.

From this perspective it is very frustrating to see positions against nested architecture put forth without alternatives that address this level of complexity being provided. To a beginner coming from React, “just use view functions” is a very good advice. To a person that deals with this level of complexity, not so much.

4 Likes
9

I think the main problem I have with things like nax/tea-combine is that they are not very useful. You can combine a pair of TEAs which is ok. Or you can combine many TEAs, but they must all have the same model and message type, which is not very useful. Elm does not have existential types, so you cannot hide types that fall out of various implementations, in the way that you can with OO programming. I’ve experimented myself with a few TEA combinator patterns, its fun to try it out, but I just don’t feel it ever yields anything that useful.

Better to treat each case individually rather than try and build a combinator library for the general case.

I agree with Peter, nested TEA is sometimes necessary. I don’t think anyone ever said you should never do it, its just that it needs to be in its proper place further down the list of available options before you get into it. So I kind of agree, it should not be blindly encouraged without understanding the context. “I don’t think this pattern should be promoted without putting it in context alongside the alternatives.” - might be a better way to express it?

What is so bad about nested TEA anyway? I do find it useful to help organise my code and lower the complexity of parts of the code. Having a consistent ‘structural’ concept accross a project can also make it easier to navigate and understand the whole. You have to write a bit of boiler plate to put everything together, more often than not I have some handy lift combinator to do that.

Here is a Page combinator pattern I am having some fun with at the moment:

type alias Page msg cmd model =
    { subscriptions : Config -> model -> Sub cmd
    , update : Config -> msg -> model -> ( model, Cmd cmd )
    , view : ResponsiveStyle -> model -> Html cmd
    }


lift :
    (model -> submodel)
    -> (submodel -> model -> model)
    -> (subcmd -> cmd)
    -> Page submsg subcmd submodel
    -> Page submsg cmd model


type alias Layout msg cmd model =
    Page msg cmd model -> Page msg cmd model
11

Not really, this looks to me more like a Taco/SharedState situation.

Nested architecture is when you break the UI into parts and put together those parts using Cmd.map and Html.map (or some alternative pattern like providing child update and view with lift functions).

I feel like the only constructive way forward around this issue for me would be some kind of complex but realistic UI that would showcase the complexity issue. Then, that specific UI would have a first implementation that would then be refactor-able using different approaches. It would act as TodoMVC for complexity.

I would stop here for now.

12

This is exactly what I’m doing. I hoped this would be clear, based on the information I shared in the example. There is some failure of communication here :confused:

There is no issue for me, and I think I’ve shared more than enough at this point. I don’t want to lead anyone astray, and if my approach is perceived as unconstructive, simple and unrealistic, I’d rather stop here too. I respect your opinion, and we don’t need agree on all of this, for it to be good :sunny:

EDIT: I’ve decided to remove my example based on your response, to remove any chance of causing bad influence. I don’t think I’m able to communicate these ideas in a way that isn’t misinterpreted, so I’d rather be safe than sorry :slight_smile:

13

Hm, after reading the Medium post I understood, that the cause of this limitation is caused by the limit of elements within a tuple, so nested tuples are used. As far as i know in Elm is no other data-structure available or possible (due to the type-safety) that can handle records of different type and iterated / mapped despite of (nested) tuples.

It is interesting to see how simple the model used on this example is transferred into a record.

I miss a way to let these components communicate (despite of URLs and ports).

14

Have you checked glue?

2 Likes
15

Thanks, I will look at glue.

16

So “glue” is more about sending messages from child to parent using a “lift” function, as used in some UI-Libs. I searched a simple way sending messages between childs, e.g. when a form sends data to a server, an other part needs to reload the data from the server. I ended with having a single but neested Msg-type, separated in many files, because I found no other way to resolve the circular inclusions.

17

This is what I do. I use the out message pattern everywhere. I have three leverls:

Widget: full featured UI element (subscriptions, multilingual, composable, serializable (in the work) (so, customizable by the clients). A widget then can be a simple view, a view with state (an though an init and an update functions), a view with state and subscriptions, or a view with state and subscriptions that returns replies. In the begining we used the elm-reply, but we have added support for multiple replies (out msgs). Widgets are connected to server data in two stages: fetching, where we retrieve everything that is needed by any view, then, digesting the data so that intensive calculations needed by views are performed only once. Until this stage we can cache the data as part of the request. Then, the final stage with the data is mapping the data. We still have a lot of work and improvements to do. All 100% pure elm. From the composition part, we also have a subscription that any view can listen to that is called SessionUpdated, and we trigger a port that is connect directly into the subscription. All views that are interested can subscribe to that. This we only need in one place, so I don’t know how well it scales to many views. At some points we have to sacrifice static typing, but you have to anyway when you transform to string to show a text or to float when you want to draw a pixel. pixels and text are not elm types. For know it looks very promising. In short, Elm is awesome.

18

Hello, I’m the author of the mentioned Glue library and I’m also author of Haskell library that has word “combinators” in its name - aeson-combinators. For what it’s worth I can share my perspective on few of the things mentioned in this thread.

Combinators

I completely agree with all what was said above. It’s true that to some degree word “combinator” is quite under-specified - something that is quite common in programming (think of C++ std::vector or “isomorphic” applications).

I would personally define combinator as function that allows one to compose larger structure (in very abstract sense) by combining smaller pieces of the structure. The most common example of this in Elm is json Decoder which has combinators. It for instance allows to combine Decoder Int and Decoder String into Decoder of pair of those and then combinator for producing Decoder of List of those composite decoders. This is something I would expect from any API that describes itself as being combinators based. I also think such library should not be closed over specific type. Some examples of what I would call combinators based API in elm:

Glue

For better or worse the Glue library is not as much about what it provides as it is about what it encourages. I originally designed it when working on quite large and complicated single-page application in a team where many members were quite new to the functional programming. There are few things that at least I personally believe lead to more extensible and easier to work with code. Let me mention few first

Use Records not Sums (for model)

I think modeling application state as record (product) rather than sum (or enum if you like) is better. Not only that it will help you avoid akward double pattern matching on Msg constructor as well as some Page type. It’s also more accurate model. Pretending that the previous page is dead just because route change leads to limitations in functionality. Also who is to really guarantee that is the case in presence of concurrency. Furthermore modeling some sort of Page sum type breaks the single source of truth. What route is being active should be described by Route data, duplicating this information is problematic. There might still be a good reasons to choose sum type over record but I don’t think sums should be automatic default

No Triplets (in update)

This pattern was used by some folks in community for a while. I was never big fan of it. In my opinion the comunication upwards should always be async to keep dataflows simple. Otherwise the boundaries of what is touching what starts to be completely invisible in the code which makes debugging quite painful.

Avoid Types module at all cost

Another pattern I wanted to avoid (which was quite popular at some time) was splitting your app into files like this:

  • Types.elm - contains Msg and model definition to avoid circular deps (terrible on its own)
  • Update.elm - contains giant update function (which is based on Msg and Model of course)
  • View.elm - contains giant view

I disliked this type of separation with passion :smiley: To me it never made sense to “split” something into modules that all depends on each other. I think such split was actually more harmful than anything else because not only that everything depend on everything the definition of that stuff was also always in some other module.

Glue

Glue is in fact just a simple lens and not much more. Beside the definition of accessor for the nested module it only contains the function from one Msg type to the other. This is traditionally just one of the Msg constructors of a consumer/parent module. There are some neat things like id or compose function which might hint you that there is some underlying algebraic thing hidden perhaps but the functionality that glue provides is far less important or mostly equivalent to what you can get by following recommendations above. Perhaps with addition of:

  • in any exposed function your last argument should be model
  • you can forget about field and Msg constructor names and remember just name of glue type
  • when combining a lot of these things it feels just a tiny bit more compositional

I can’t compare it to tea-combine library because I did not know it but I think it’s cool to see people trying new ways of doing things.

All comments above are my personal opinions based on my personal biases jadyjadydada. If anything I think we should avoid being too emotionally attached to any particular way of doing / naming things. Point should be to try to improve and help the community, not to have flame wars because our ego is too attached to some way of structuring code over the other.

2 Likes
19

I like structuring apps using the triplet pattern where the last item is a list of global actions. It makes perfect sense to me and I will happily recommend this way of doing things as it has worked very well for us.

Do you have an example of how do you prefer to do it?

20

I’m not fond of having Update.elm or View.elm. But Types.elm seems necessary to me many times. Consider that you have a huge module and you want to split your views. Then you will need to put your types somewhere to avoid circular dependencies. And you have a dozen types. What do you do?

21

I like structuring apps using the triplet pattern where the last item is a list of global actions.

The reason why I default to triggering Cmds is because that way there is widely known structure automatically available. By that I mainly mean Cmd.batch and Cmd.none which let you compose these things in Monoidic way (Cmd.none being identity and Cmd.batch being variant of binary operation). Without this structure I would need to define some Free structure around the action type by which point I would be asking myself if it would not make more sense to use some Free monad based approach like Halogen. For instance you can look into the actual implementation of glue to see how it leverages this structure of Cmd type.

It also seems to be more natural for people used to elm. Like seeing Msgs being sent when debugging and having a less back and forth type of control flow.

Downside of the Cmd approach is that it triggers multiple calls of update and thus even render and view functions. But that rarely if ever was a problem in apps I worked on.

Do you have an example of how do you prefer to do it?

You can check this GitHub - turboMaCk/glue: Composing TEA modules with isolated state it contains example.

But Types.elm seems necessary to me many times. Consider that you have a huge module and you want to split your views.

The pattern I use is to pass constructors of type as functions into such view. Usually as part of some record which I like to call Config.

import Html
import Html.Events as Events

type alias Config msg =
    { action : String -> msg
    , cancel : msg
    }

type alias State =
   { value : String }

{-| Reusable view that knows nothing about Msg type -}
view : Config msg -> State -> Html msg
view config state =
  Html.div []
    [ Html.button [ Events.onClick config.cancel ]
        [Html.text "Cancel" ]
    , Html.button [ Events.onClick <| config.action state.value ]
        [Html.text <| "Perform " ++ state.value ]
    ]

Just keep in mind that Html.Lazy is using referential equality under the hood and calling this view as Cancelable.view { action = Store, cancel = Discard } value won’t work with it. So if you want to use Html.Lazy with this pattern you need to extract the config definition to constant. This is also why I always recommend to keep it static and avoid constructing it from data in Model.

@Janiczek said to me just few days ago that he really likes this pattern and that it makes a lot of stuff quite simple and modular. So perhaps he might have something to add to this?

EDIT: Also maybe worth noting that I personally would rather work with 10k LOC single module than with 10 1k modules which are closed over same type. The benefit of splitting the source code is almost nonexistent it seems to me. Unless the concrete types are abstracted out I don’t think splitting to files can help much.

2 Likes
22

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.