# Construct monad in \`sicp-pict\`? **URL:** \ **Category:** Show & Tell\ **Tags:** typed-racket, sicp, functor, monad, category\ **Created:** [May 8, 2022, 12:53pm UTC](https://racket.discourse.group/t/construct-monad-in-sicp-pict/985 "2022-05-08T12:53:57Z")\ **Posts on this page:** 6\ **Page:** 1

**Author:** ![NoahStoryM](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/noahstorym/32/17_2.png) [@NoahStoryM](https://racket.discourse.group/u/NoahStoryM)\ **Post date:** [May 8, 2022, 12:53pm UTC](https://racket.discourse.group/t/construct-monad-in-sicp-pict/985/1 "2022-05-08T12:53:57Z")

In the current `sicp-pict`, we treat a picture as a painter, which is a procedure that takes a frame and then draws the picture to a bitmap (so we don't care about its return value, any type is ok). I tried to define a procedure called `apply-painter`, which takes a painter and a frame and returns a bitmap: ```scheme (define (apply-painter painter frame #:width [width 200] #:height [height 200]) (define-values (bm dc) (make-painter-bitmap width height)) (begin0 bm (parameterize ([current-bm bm] [current-dc dc]) ;; TODO Apply frame's transformation to bitmap. (send dc scale 0.99 0.99) ; make the entire unit square visible (painter frame)))) (define unit-frame (frame (vect 0. 0.) (vect 1. 0.) (vect 0. 1.))) (define (paint painter #:width [width 200] #:height [height 200]) (make-object image-snip% (apply-painter painter unit-frame #:width width #:height height))) ``` With `apply-painter`, we can treat a painter as a procedure that takes a frame and returns a bitmap. If we regard the type of painter as follow: ```scheme (define-type (Bitmap A) ((Instance Bitmap%))) (define-type Painter (-> Frame (Bitmap Frame))) ``` Things seem to get interesting: We can define a transformation `f` between `Frame`s (marked `F`), and define a transformation `b` between `(Instance Bitmap%)`s (marked `B`), what if we then define a procedure `fmap` that maps `f` to `b`? ```scheme p F -----> B(F) = B | | | fmap | f | -----> | b = fmap(f) | | | | ∨ ∨ F -----> B(F) = B p p F -----> B(F) = B | | | fmap | p | -----> | fmap(p) | | | | ∨ ∨ B -----> B(B) = B fmap(p) ``` I'm not familiar with purely functional languages, but I guess we defined a functor this way? Then we may be able to construct monad: ```scheme (define-type (Bitmap A) (Instance Bitmap%)) (define-type Painter (-> Frame (Bitmap Frame))) (: fmap (case-> [-> (-> Frame Frame) (-> (Bitmap Frame) (Bitmap Frame))] [-> (-> Frame (Bitmap Frame)) (-> (Bitmap Frame) (Bitmap (Bitmap Frame)))])) (define fmap #;TODO) (: return Painter) (define return (compose)) (: join (-> (Bitmap (Bitmap Frame)) (Bitmap Frame))) (define join identity) (: compose (-> Painter * Painter)) (define compose superpose) (: bind (-> (Bitmap Frame) Painter (Bitmap Frame))) (define bind (λ (bm p) (join ((fmap p) bm)))) ``` ---

**Author:** ![scolobb](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/scolobb/32/108_2.png) [@scolobb](https://racket.discourse.group/u/scolobb)\ **Post date:** [May 8, 2022, 11:09pm UTC](https://racket.discourse.group/t/construct-monad-in-sicp-pict/985/2 "2022-05-08T23:09:14Z")

That's an interesting question, which in my head relates rather specifically to Haskell, as other (purely) functional languages do not elevate monads to so high an esteem. Technically speaking, you need more than a functor to construct a monad. In Haskell, the [`Monad`](https://hackage.haskell.org/package/base-4.16.1.0/docs/Prelude.html#t:Monad) type class derives from the [`Applicative`](https://hackage.haskell.org/package/base-4.16.1.0/docs/Prelude.html#t:Applicative) type class. The page [Applicative functor - HaskellWiki](https://wiki.haskell.org/Applicative_functor) summarizes quite nicely the relationship between `Functor`, `Applicative`, and `Monad`. On the immediate technical side, being able to define certain functions (e.g. `bind`) is not sufficient for your type to qualify for a monad; you also have to ensure that some additional identities hold (which I didn't verify for your example). * * * On the paradigm level, I currently have the impression that monads are particularly useful and respected in Haskell because the type system of the language is intentionally very rigid. As one consequence, mixing a debug `println` into your code is quite non-trivial because of the side-effects, and in particular taints the type of the whole function with the `IO` monad. Now monads have the cool advantage of being very explicit, and the rigid type system in Haskell ensures that you _must_ use a monad if you want _any_ side-effect, which allows you to reason quite a long way about the code without actually running it (unless you put everything in `IO`, which many people actually do, sometimes for the valid reason of reducing code complexity). Hovewer, I have the impression that it's not necessarily or generally a Rackety way of seeing or doing things. In Racket, if I want to do a `displayln` in my function, I just do it, and it doesn't need to influence the return type. That gives me weaker guarantees about my code, but is less intrusive in many subtle ways. This is, by the way, one of the main reasons why I dropped Haskell for Racket, and why I don't regret the move. I hope people with more experience with Racket will chime in and give their opinion on the matter. * * * By the way, I am quite interested in [Qi: A Functional, Flow-Oriented DSL](https://docs.racket-lang.org/qi/index.html) which allows threading data through computation in ways which I find highly superior to monads. Qi looks a little bit like [Arrows: A General Interface to Computation](https://www.haskell.org/arrows/) , but without the rigid type system burden. To me, one ultimate thing to do is to build Typed Qi, which should be possible, but probably highly non-trivial. Still, I find that Qi is a more Rackety way to thread computation than monads. ---

**Author:** ![NoahStoryM](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/noahstorym/32/17_2.png) [@NoahStoryM](https://racket.discourse.group/u/NoahStoryM)\ **Post date:** [May 9, 2022, 2:12pm UTC](https://racket.discourse.group/t/construct-monad-in-sicp-pict/985/3 "2022-05-09T14:12:16Z")

Hi @scolobb, thanks a lot for recommend me qi! qi is really excellent! I've read its document and lots of ideas come to me! I'd like to share them. 🙂 * * * Start with the thoughts I experienced when I tried construct monad in `sicp-pict`: At first I noticed that a painter is essentially a side effect of drawing on a bitmap, and I wondered if I could convert it to a function that returns a bitmap. Inspired by Cartesian closed category, I realized that I needed an `apply` function. With this `apply`, I could regard painter as a mapping from frame to bitmap, which is composable (by `superpose`) and there is an identity element of `superpose` -- `blank` (draw nothing)! Which means it's monoid! It drives me to construct monad. Based on it, I defined `fmap`, etc. and to my surprise, I thought I knew their semantics (even if I didn't prove that it's monad, I just tried to write them). - fmap: Map the transformation between frames to the transformation between bitmaps, or map the procedure of drawing on a frame to the procedure of drawing directly on a bitmap. - compose: superpose pictures together. - return: blank picture. - join: the picture drawn on a bitmap is also a bitmap. - bind: like `apply-painter` treats painter as a mapping from frame to bitmap, `bind` treats painter as a mapping from bitmap to bitmap. Proving "painter is monad" seems not to be so important -- we've defined these useful operator based on the idea. Thinking back, in the original design of `sicp-pict`, we regard picture as a process of drawing something with a frame. By this way, we only need to transform the frame to get the corresponding bitmap (similar to regard vector as the linear combination of bases in linear algebra). We transform bitmap by transforming frame, but don't forget that we can transform bitmap directly! There must be some kind of connection between frame transformation and bitmap transformation! On the other hand, we can regard painter as a function that paints picture on a frame to get a bitmap. Can we let the painter paint directly on a bitmap? Wow, that's the `bind` I defined at the beginning! * * * Here are some thoughts I got while studying category theory: Can we move the abstraction and combinations in category theory to programming languages? If we can, to what category corresponding? My answer to the 2nd question is that each type constructor (such as `Boxof`) corresponds to a category, whose object is the `Values` composed of the `Box` type, and morphism is the mapping between these `Values`. We can construct 2 special type constructors, one of them is identity type constructor: ```scheme (define-type (Id A) A) ``` With `Id`, we can regard any type `A` as `(Id A)`, which is an object in `Id` category! And the type of any function not only can be regarded as a morphism between `Values` in `Id`, but also an endofunctor from `Id` to `Id`! Another one is constant constructor (bitmap as an example): ```scheme (define-type (Bitmap) Frame) (define-type (Bitmap A) (Instance Bitmap%)) ``` And if we regard any constant `b` with type `B` as a function of type `(-> (Values 1) (Values B))` (marked `(-> 1 B)`), which is an endofunctor in Id, then original morphism in Id (like f : `(-> B C)`) become a natural transformation `(-> (-> 1 B) (-> 1 C))`. So that any value of `Frame` can be regard as an endofunctor I = T^0 (mean no picture), of `(Instance Bitmap%)` can be regard as T(I) = T^1 (mean paint something in a frame T^0), and T(T(I)) = T^2 (mean paint something in a bitmap T^1), etc. Then we can define `η : I → T` as blank (a painter that paint nothing on frame), `μ : T × T → T` as identity (a bitmap painted something is also a bitmap), and they satisfy these laws: ```scheme μ ∘ Tμ = μ ∘ μT μ ∘ Tη = μ ∘ ηT = 1 ``` * * * I'm not sure how category is used in purely functional language like Haskell, but I believe the essence of category theory is compose. `qi` provides a very elegant and intuitive way to compose! I'd like to build typed qi too, but I suspect it's not that easy. In fact, I tried something and found that the existing type system has many restrictions on composition, see TR issues: 1172, 1175, 1176, 1218. I think that the implementation of qi is based on the assumption that functions are mappings between `Values`, but unfortunately TR's type system (and contract system) doesn't see it that way. TR has done a lot to the argument types in `->` rather than to `Values`, thus it restricts the return types. I plan to study how contract system works and try to define contract for values, and then based on it to improve `Values` in TR, so that we can construct something like `(Values (Values Symbol String) *)`, which can be used as argument type or return type. And I guess `Values` can also guide how to extend the Read and Write type in the future. ---

**Author:** ![countvajhula](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/countvajhula/32/65_2.png) [@countvajhula](https://racket.discourse.group/u/countvajhula)\ **Post date:** [May 12, 2022, 1:43pm UTC](https://racket.discourse.group/t/construct-monad-in-sicp-pict/985/4 "2022-05-12T13:43:58Z")

Oh man, there's a lot here -- this is going to be a long, multi-part response. This will cover (1) Arrows, (2) Monads in Haskell vs Qi, (3) Typed Qi. @NoahStoryM I'm loving the thought process that went into your characterization above, thank you for sharing and for taking such care to draw diagrams. First off, I'd love to learn more about Haskell but it is dense and I haven't had the opportunity to use it for anything before. This thread has inspired me to resume my learning of it 🙂 I looked into Arrows and found [this great description](https://wiki.haskell.org/Typeclassopedia#Intuition_5) in the Typeclassopedia to supplement the link you sent @scolobb . I'm frankly a bit mindblown by the correspondence between Qi and Arrows here -- to me there doesn't seem to be any special reason why they ought to correspond so exactly, and yet: - The `arr` method corresponds to Qi's "base case" of [treating any function as a flow](https://docs.racket-lang.org/qi/Introduction_and_Usage.html#%28part._.What_is_a_.Flow_%29). - `(>>>)` is equivalent to [`~>`](https://docs.racket-lang.org/qi/Language_Interface.html#%28form._%28%28lib._qi%2Fmain..rkt%29._~7e~3e%29%29) - `first`, `second`, and their composite `(***)` is the [relay](https://docs.racket-lang.org/qi/Qi_Forms.html#%28part._.Routing%29) -- i.e. `(== a _)`, `(== _ b)`, and `(== a b)`, respectively. - `(&&&)` referred to as "fanout composition" is exactly the [tee junction](https://docs.racket-lang.org/qi/Qi_Forms.html#%28part._.Routing%29), `(-< f g)` I suppose the reason for this close correspondence might be that, in designing these combinators, I couldn't think of any other ways to compose functions, and perhaps these really are all of the foundational (in whatever sense) ones. I did at one time also consider a "diamond" composition, `<>`, since it was the only shape missing in `~>` `-<` `><` `==`, but I forget now what it did (or maybe I couldn't think of what it ought to do!). It probably was reducible to one of these other combinators and was not truly distinct (for that matter, while `><` is reducible to `==` when the number of values is known, this is often not the case since the number varies at runtime -- so `><` may be a distinct primitive that isn't possible in statically typed languages). Thank you for making this connection - it is valuable! This will surely provide some clarity on the theoretical underpinnings, scope, and limitations of Qi (some of which we will return to on the subject of monads, below). For some time now I've had the vague suspicion that some language features that are arcane in other languages could be simple in Qi (and vice versa). Arrows is clearly one of these, and I've also felt that monads would be, too, where for instance, [Qi's treatment of Maybe](https://docs.racket-lang.org/qi/Qi_Macros.html#%28part._.Write_.Yourself_a_.Maybe_.Monad_for_.Great_.Good%29) in terms of presence or absence of values rather than annotations like `Just` and _reified_ absence values like `Nothing`, seems to me to be more elegant (and, incidentally, this approach was inspired by buddhist sunyata logic -- what could be called "logical zero"). I suspect, but don't know for sure as my category theory is rudimentary, that this approach can generalize in a natural way to at least some other monads -- for instance, just as Maybe is presence or absence of a value, the State monad could be represented as the presence and persistence of additional values (fulfilling, of course, the necessary formal properties). IO may be the spontaneous addition of new values (functions with outputs but no inputs) in some form, and grounded side effects (functions with inputs but no outputs) that produce no values. The unifying theme here being the creation, existence or absence (and consequently also the _number_), and the termination of _values_. Of course, the monad laws would need to be proved in each case, and it would be interesting to see whether in fact every monad could be expressed in this way. If indeed Qi is Arrows, then [this SO post](https://stackoverflow.com/questions/3652054/monads-vs-arrows) seems to suggest that the answer is in the negative here. On the other hand, I found the [original paper on Arrows](http://www.cse.chalmers.se/~rjmh/Papers/arrows.pdf), which concludes, "We have seen that any monadic library can be given an arrow interface instead (via Kleisli arrows), and so the arrow interface is strictly more general." In any case, as Qi also has a lot of features that don't necessarily reduce to the combinators discussed above, perhaps it is not "only" Arrows, and this would in that case be a theoretical lower bound on expressiveness. To digress further on this subject, another language feature that is potentially "natural" in Qi is delimited continuations. I think in Qi they manifest simply as a "potential difference" between two points in a flow (like the concept in physics for electromagnetic fields), which is itself expressible as a flow, i.e. a function. It may be that Qi would be a good language for studying continuations as this manifestation is very natural and easy to think about -- maybe even affording a mathematical formulation that maps directly to Qi code. Just a vague idea at this stage! Finally, returning to Typed Qi, that would indeed be an interesting project, and one that I incidentally [created an issue for](https://github.com/countvajhula/qi/issues/18) when you first mentioned it a little while back 🙂 . I recently came across this project called [Turnstile](https://github.com/stchang/macrotypes) that may be relevant 🤷 ---

**Author:** ![scolobb](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/scolobb/32/108_2.png) [@scolobb](https://racket.discourse.group/u/scolobb)\ **Post date:** [May 21, 2022, 11:55am UTC](https://racket.discourse.group/t/construct-monad-in-sicp-pict/985/5 "2022-05-21T11:55:08Z")

Hi @NoahStoryM and sorry for the delay with the answer. The times are busy for me right now, so I waited until I could invest serious thinking into this. I will comment on some of the points you are making, under the disclaimer that I am not a specialist in programming language theory, lambda calculus, category theory, or types. By the way, I am really enjoying this discussion 🙂 * * * > [@NoahStoryM](#): > > Inspired by Cartesian closed category I checked out [Cartesian closed category - Wikipedia](https://en.wikipedia.org/wiki/Cartesian_closed_category) to refresh my memory, and incidentally it says: > These categories are particularly important in [mathematical logic](https://en.wikipedia.org/wiki/Mathematical_logic) and the theory of programming, in that their [internal language](https://en.wikipedia.org/wiki/Internal_language) is the [simply typed lambda calculus](https://en.wikipedia.org/wiki/Simply_typed_lambda_calculus). which is probably why you brought up the term in the discussion in the first place. > [@NoahStoryM](#): > > Proving "painter is monad" seems not to be so important -- we've defined these useful operator based on the idea. OK, I get your point and agree with it. > [@NoahStoryM](#): > > Can we move the abstraction and combinations in category theory to programming languages? If we can, to what category corresponding? This makes me think of [Hask - HaskellWiki](https://wiki.haskell.org/Hask), " the category of Haskell types and functions." > [@NoahStoryM](#): > > My answer to the 2nd question is that each type constructor (such as `Boxof` ) corresponds to a category, whose object is the `Values` composed of the `Box` type, and morphism is the mapping between these `Values` . I don't know if I follow everything correctly, but I will assume that the objects in this category are the types `(Boxof a)` and that the morphisms are the functions with the types `(-> (Boxof a) (Boxof b))`. I am more used to putting the whole of a language with all its types into a category and reasoning inside, but I guess you are right: a type constructor may be seen as inducing a subcategory of that big category, provided that you ensure the morphisms are properly conserved. > [@NoahStoryM](#): > > And the type of any function not only can be regarded as a morphism between `Values` in `Id` , but also an endofunctor from `Id` to `Id` ! I don't think I follow. A functor between categories _A_ and _B_ is a pair of mappings, one between the objects of _A_ and the objects _B_, and the other between the morphisms of _A_ and _B_. In your case, _A_ = _B_ = `Id`. Consider a function `f : a → b`. What such pair of mappings between `Id` and `Id` does it induce? > [@NoahStoryM](#): > > I believe the essence of category theory is compose I'm not sure what you mean. Morphism composability (associativity and identity element) is indeed part of the very definition of a category, but to me it is the higher-level concepts arising from those basic definitions which are more interesting. > [@NoahStoryM](#): > > I'd like to build typed qi too, but I suspect it's not that easy. In fact, I tried something and found that the existing type system has many restrictions on composition, see TR issues: 1172, 1175, 1176, 1218. Yeah, I agree. With community help, I threw together a [couple of macros](https://pkgs.racket-lang.org/package/typed-compose) to make chaining multiple functions more practical, but getting from there to Qi is a long shot. My impression on the other hand is that Typed Racket is getting a little bit of an unequal treatment, because it builds upon an existing language known for its high flexibility, which naturally makes things much harder to type than, say, in Haskell, whether the whole language was designed from the ground up to work well with a certain type system. > [@NoahStoryM](#): > > I plan to study how contract system works and try to define contract for values, and then based on it to improve `Values` in TR, Good luck with that, and do give some feedback on the forum here 🙂 ---

**Author:** ![scolobb](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/scolobb/32/108_2.png) [@scolobb](https://racket.discourse.group/u/scolobb)\ **Post date:** [May 21, 2022, 10:00pm UTC](https://racket.discourse.group/t/construct-monad-in-sicp-pict/985/6 "2022-05-21T22:00:06Z")

Hi @countvajhula, and sorry for the late answer. I waited until I had enough time to properly read, think, and answer to your message. EDIT: Sorry, I initially posted a half-finished message because my fingers slipped 😃 * * * > [@countvajhula](#): > > First off, I'd love to learn more about Haskell but it is dense and I haven't had the opportunity to use it for anything before. Yeah, Haskell is very dense, but I believe that programming in this language gave me some discipline and insight which I couldn't have got otherwise. Still, today Racket is my favorite language 😃 > [@countvajhula](#): > > I suppose the reason for this close correspondence might be that, in designing these combinators, I couldn't think of any other ways to compose functions, and perhaps these really are all of the foundational (in whatever sense) ones. I think you are right: Qi has the goal of composing computation transparently (i.e., without unpacking the values too much), and it's exactly the goal of `Arrows`. Since both Qi and `Arrows` are designed in a functional programming context, it is probably not that surprising that there are a lot of coincidences. > [@countvajhula](#): > > For some time now I've had the vague suspicion that some language features that are arcane in other languages could be simple in Qi (and vice versa). I share that intuition as well. I think one of the reasons for some things being simpler in Qi goes down to the flexibility of Racket. > [@countvajhula](#): > > [Qi's treatment of Maybe](https://docs.racket-lang.org/qi/Qi_Macros.html#%28part._.Write_.Yourself_a_.Maybe_.Monad_for_.Great_.Good%29) in terms of presence or absence of values rather than annotations like `Just` and _reified_ absence values like `Nothing` , seems to me to be more elegant That's interesting, thank you for the reference! I even think that in Qi the need for the `Maybe` monad is lesser, because there seem to be other ways to deal with cases with which it deals in e.g. Haskell. > [@countvajhula](#): > > (and, incidentally, this approach was inspired by buddhist sunyata logic -- what could be called "logical zero") Very interesting! I'd be curious to discuss this with you, but probably on a different channel. > [@countvajhula](#): > > I suspect, but don't know for sure as my category theory is rudimentary, that this approach can generalize in a natural way to at least some other monads To me, monads in computing are a tool which allows to formally capture _some_ aspects of composition of computation. Monads allow reasoning about the code without actually executing, which is sometimes really practical, especially when side effects are involved. There are other tools for composing computation which have less nice formal properties, but which on the other hand are way more practical. As a trivial example I like to cite is putting debug output in your code. In Racket it may be as simple as adding a `print` / `display` in your function, while in a strictly monad-focused language such as Haskell this taints the type of the function and the type of _all calling functions_ with the `IO` monad. (There is of course [Debug.Trace](https://hackage.haskell.org/package/base-4.16.1.0/docs/Debug-Trace.html), but it kind of proves the point: you essentially have to escape the type system if you want to do debug output without too much refactoring.) My opinion is that Qi should be able to easily generalize all interesting monad use cases (I speak here after having skimmed a Qi tutorial without actually doing the exercises 😃 ), but will at the same type give up on some formal properties of the programs. > [@countvajhula](#): > > If indeed Qi is Arrows, then [this SO post](https://stackoverflow.com/questions/3652054/monads-vs-arrows) seems to suggest that the answer is in the negative here. On the other hand, I found the [original paper on Arrows](http://www.cse.chalmers.se/~rjmh/Papers/arrows.pdf), which concludes, "We have seen that any monadic library can be given an arrow interface instead (via Kleisli arrows), and so the arrow interface is strictly more general." From what I remember, arrows generalize monads in some way, and as I stated above I believe that Qi has better compositional properties, and loses some formal properties (as often happens with generalizations). > [@countvajhula](#): > > To digress further on this subject, another language feature that is potentially "natural" in Qi is delimited continuations. Oh, I guess you are right! I have read some discussions about continuations here, some docs here and there, and listened to some presentations, but they have been systematically out of my use cases. I promised myself that the next time I need to exit a nested loop, I will definitely use continuations instead of some additional Boolean flags 😃 > [@countvajhula](#): > > Finally, returning to Typed Qi, that would indeed be an interesting project, and one that I incidentally [created an issue for](https://github.com/countvajhula/qi/issues/18) when you first mentioned it a little while back 🙂 Woow, cool! Liked and subscribed 😃 > [@countvajhula](#): > > I recently came across this project called [Turnstile](https://github.com/stchang/macrotypes) that may be relevant 🤷 Oh, I looked through the docs for Turnstile a couple of times, but I couldn't yet see an immediate application. But you are right, it does seem very relevant to the potential Typed Qi project!