Applicative programming with effects

import%20marimo%0A%0A__generated_with%20%3D%20%220.13.4%22%0Aapp%20%3D%20marimo.App(app_title%3D%22Applicative%20programming%20with%20effects%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Applicative%20programming%20with%20effects%0A%0A%20%20%20%20%20%20%20%20%60Applicative%20Functor%60%20encapsulates%20certain%20sorts%20of%20*effectful*%20computations%20in%20a%20functionally%20pure%20way%2C%20and%20encourages%20an%20*applicative*%20programming%20style.%0A%0A%20%20%20%20%20%20%20%20Applicative%20is%20a%20functor%20with%20application%2C%20providing%20operations%20to%0A%0A%20%20%20%20%20%20%20%20%2B%20embed%20pure%20expressions%20(%60pure%60)%2C%20and%0A%20%20%20%20%20%20%20%20%2B%20sequence%20computations%20and%20combine%20their%20results%20(%60apply%60).%0A%0A%20%20%20%20%20%20%20%20In%20this%20notebook%2C%20you%20will%20learn%3A%0A%0A%20%20%20%20%20%20%20%201.%20How%20to%20view%20%60Applicative%60%20as%20multi-functor%20intuitively.%0A%20%20%20%20%20%20%20%202.%20How%20to%20use%20%60lift%60%20to%20simplify%20chaining%20application.%0A%20%20%20%20%20%20%20%203.%20How%20to%20bring%20*effects*%20to%20the%20functional%20pure%20world.%0A%20%20%20%20%20%20%20%204.%20How%20to%20view%20%60Applicative%60%20as%20a%20lax%20monoidal%20functor.%0A%20%20%20%20%20%20%20%205.%20How%20to%20use%20%60Alternative%60%20to%20amalgamate%20multiple%20computations%20into%20a%20single%20computation.%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20details%20%7C%20Notebook%20metadata%0A%20%20%20%20%20%20%20%20%20%20%20%20type%3A%20info%0A%0A%20%20%20%20%20%20%20%20version%3A%200.1.3%20%7C%20last%20modified%3A%202025-04-16%20%7C%20author%3A%20%5Bm%C3%A9taboulie%5D(https%3A%2F%2Fgithub.com%2Fmetaboulie)%3Cbr%2F%3E%0A%20%20%20%20%20%20%20%20reviewer%3A%20%5BHaleshot%5D(https%3A%2F%2Fgithub.com%2FHaleshot)%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20The%20intuition%3A%20%5BMultifunctor%5D(https%3A%2F%2Farxiv.org%2Fpdf%2F2401.14286)%0A%0A%20%20%20%20%20%20%20%20%23%23%20Limitations%20of%20functor%0A%0A%20%20%20%20%20%20%20%20Recall%20that%20functors%20abstract%20the%20idea%20of%20mapping%20a%20function%20over%20each%20element%20of%20a%20structure.%0A%0A%20%20%20%20%20%20%20%20Suppose%20now%20that%20we%20wish%20to%20generalise%20this%20idea%20to%20allow%20functions%20with%20any%20number%20of%20arguments%20to%20be%20mapped%2C%20rather%20than%20being%20restricted%20to%20functions%20with%20a%20single%20argument.%20More%20precisely%2C%20suppose%20that%20we%20wish%20to%20define%20a%20hierarchy%20of%20%60fmap%60%20functions%20with%20the%20following%20types%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20fmap0%20%3A%3A%20a%20-%3E%20f%20a%0A%0A%20%20%20%20%20%20%20%20fmap1%20%3A%3A%20(a%20-%3E%20b)%20-%3E%20f%20a%20-%3E%20f%20b%0A%0A%20%20%20%20%20%20%20%20fmap2%20%3A%3A%20(a%20-%3E%20b%20-%3E%20c)%20-%3E%20f%20a%20-%3E%20f%20b%20-%3E%20f%20c%0A%0A%20%20%20%20%20%20%20%20fmap3%20%3A%3A%20(a%20-%3E%20b%20-%3E%20c%20-%3E%20d)%20-%3E%20f%20a%20-%3E%20f%20b%20-%3E%20f%20c%20-%3E%20f%20d%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20And%20we%20have%20to%20declare%20a%20special%20version%20of%20the%20functor%20class%20for%20each%20case.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Defining%20Multifunctor%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%0A%20%20%20%20%20%20%20%20we%20use%20prefix%20%60f%60%20rather%20than%20%60ap%60%20to%20indicate%20*Applicative%20Functor*%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20As%20a%20result%2C%20we%20may%20want%20to%20define%20a%20single%20%60Multifunctor%60%20such%20that%3A%0A%0A%20%20%20%20%20%20%20%201.%20Lift%20a%20regular%20n-argument%20function%20into%20the%20context%20of%20functors%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20lift%20a%20regular%203-argument%20function%20%60g%60%0A%20%20%20%20%20%20%20%20%20%20%20%20g%3A%20Callable%5B%5BA%2C%20B%2C%20C%5D%2C%20D%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20into%20the%20context%20of%20functors%0A%20%20%20%20%20%20%20%20%20%20%20%20fg%3A%20Callable%5B%5BFunctor%5BA%5D%2C%20Functor%5BB%5D%2C%20Functor%5BC%5D%5D%2C%20Functor%5BD%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%203.%20Apply%20it%20to%20n%20functor-wrapped%20values%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20fa%3A%20Functor%5BA%5D%2C%20fb%3A%20Functor%5BB%5D%2C%20fc%3A%20Functor%5BC%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20fg(fa%2C%20fb%2C%20fc)%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%205.%20Get%20a%20single%20functor-wrapped%20result%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%20%20%20%20fd%3A%20Functor%5BD%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20We%20will%20define%20a%20function%20%60lift%60%20such%20that%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20fd%20%3D%20lift(g%2C%20fa%2C%20fb%2C%20fc)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Pure%2C%20apply%20and%20lift%0A%0A%20%20%20%20%20%20%20%20Traditionally%2C%20applicative%20functors%20are%20presented%20through%20two%20core%20operations%3A%0A%0A%20%20%20%20%20%20%20%201.%20%60pure%60%3A%20embeds%20an%20object%20(value%20or%20function)%20into%20the%20applicative%20functor%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20a%20-%3E%20F%20a%0A%20%20%20%20%20%20%20%20%20%20%20%20pure%3A%20Callable%5B%5BA%5D%2C%20Applicative%5BA%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20for%20example%2C%20if%20%60a%60%20is%0A%20%20%20%20%20%20%20%20%20%20%20%20a%3A%20A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20then%20we%20can%20have%20%60fa%60%20as%0A%20%20%20%20%20%20%20%20%20%20%20%20fa%3A%20Applicative%5BA%5D%20%3D%20pure(a)%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20or%20if%20we%20have%20a%20regular%20function%20%60g%60%0A%20%20%20%20%20%20%20%20%20%20%20%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20then%20we%20can%20have%20%60fg%60%20as%0A%20%20%20%20%20%20%20%20%20%20%20%20fg%3A%20Applicative%5BCallable%5B%5BA%5D%2C%20B%5D%5D%20%3D%20pure(g)%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%202.%20%60apply%60%3A%20applies%20a%20function%20inside%20an%20applicative%20functor%20to%20a%20value%20inside%20an%20applicative%20functor%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20F%20(a%20-%3E%20b)%20-%3E%20F%20a%20-%3E%20F%20b%0A%20%20%20%20%20%20%20%20%20%20%20%20apply%3A%20Callable%5B%5BApplicative%5BCallable%5B%5BA%5D%2C%20B%5D%5D%2C%20Applicative%5BA%5D%5D%2C%20Applicative%5BB%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20and%20we%20can%20have%0A%20%20%20%20%20%20%20%20%20%20%20%20fd%20%3D%20apply(apply(apply(fg%2C%20fa)%2C%20fb)%2C%20fc)%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%0A%20%20%20%20%20%20%20%20As%20a%20result%2C%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20lift(g%2C%20fa%2C%20fb%2C%20fc)%20%3D%20apply(apply(apply(pure(g)%2C%20fa)%2C%20fb)%2C%20fc)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%20%7C%20How%20to%20use%20*Applicative*%20in%20the%20manner%20of%20*Multifunctor*%0A%0A%20%20%20%20%20%20%20%201.%20Define%20%60pure%60%20and%20%60apply%60%20for%20an%20%60Applicative%60%20subclass%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20We%20can%20define%20them%20much%20easier%20compared%20with%20%60lift%60.%0A%0A%20%20%20%20%20%20%20%202.%20Use%20the%20%60lift%60%20method%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20We%20can%20use%20it%20much%20more%20convenient%20compared%20with%20the%20combination%20of%20%60pure%60%20and%20%60apply%60.%0A%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20attention%20%7C%20You%20can%20suppress%20the%20chaining%20application%20of%20%60apply%60%20and%20%60pure%60%20as%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20apply(pure(g)%2C%20fa)%20-%3E%20lift(g%2C%20fa)%0A%20%20%20%20%20%20%20%20apply(apply(pure(g)%2C%20fa)%2C%20fb)%20-%3E%20lift(g%2C%20fa%2C%20fb)%0A%20%20%20%20%20%20%20%20apply(apply(apply(pure(g)%2C%20fa)%2C%20fb)%2C%20fc)%20-%3E%20lift(g%2C%20fa%2C%20fb%2C%20fc)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Abstracting%20applicatives%0A%0A%20%20%20%20%20%20%20%20We%20can%20now%20provide%20an%20initial%20abstraction%20definition%20of%20applicatives%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%40dataclass%0A%20%20%20%20%20%20%20%20class%20Applicative%5BA%5D(Functor%2C%20ABC)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20pure(cls%2C%20a%3A%20A)%20-%3E%20%22Applicative%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20NotImplementedError(%22Subclasses%20must%20implement%20pure%22)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20apply(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fg%3A%20%22Applicative%5BCallable%5B%5BA%5D%2C%20B%5D%5D%22%2C%20fa%3A%20%22Applicative%5BA%5D%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%20-%3E%20%22Applicative%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20NotImplementedError(%22Subclasses%20must%20implement%20apply%22)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20lift(cls%2C%20f%3A%20Callable%2C%20*args%3A%20%22Applicative%22)%20-%3E%20%22Applicative%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20curr%20%3D%20cls.pure(f)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20curr%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20arg%20in%20args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20curr%20%3D%20cls.apply(curr%2C%20arg)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20curr%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20attention%20%7C%20minimal%20implementation%20requirement%0A%0A%20%20%20%20%20%20%20%20-%20%60pure%60%0A%20%20%20%20%20%20%20%20-%20%60apply%60%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%23%20Instances%2C%20laws%20and%20utility%20functions%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Applicative%20instances%0A%0A%20%20%20%20%20%20%20%20When%20we%20are%20actually%20implementing%20an%20*Applicative*%20instance%2C%20we%20can%20keep%20in%20mind%20that%20%60pure%60%20and%20%60apply%60%20fundamentally%3A%0A%0A%20%20%20%20%20%20%20%20-%20embed%20an%20object%20(value%20or%20function)%20to%20the%20computational%20context%0A%20%20%20%20%20%20%20%20-%20apply%20a%20function%20inside%20the%20computation%20context%20to%20a%20value%20inside%20the%20computational%20context%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20The%20Wrapper%20Applicative%0A%0A%20%20%20%20%20%20%20%20-%20%60pure%60%20should%20simply%20*wrap*%20an%20object%2C%20in%20the%20sense%20that%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20%20%20%20%20Wrapper.pure(1)%20%3D%3E%20Wrapper(value%3D1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20%60apply%60%20should%20apply%20a%20*wrapped*%20function%20to%20a%20*wrapped*%20value%0A%0A%20%20%20%20%20%20%20%20The%20implementation%20is%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(A%2C%20Applicative%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Wrapper%5BA%5D(Applicative)%3A%0A%20%20%20%20%20%20%20%20value%3A%20A%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20pure(cls%2C%20a%3A%20A)%20-%3E%20%22Wrapper%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(a)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20apply(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fg%3A%20%22Wrapper%5BCallable%5B%5BA%5D%2C%20B%5D%5D%22%2C%20fa%3A%20%22Wrapper%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Wrapper%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(fg.value(fa.value))%0A%20%20%20%20return%20(Wrapper%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%3E%20try%20with%20Wrapper%20below%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Wrapper)%3A%0A%20%20%20%20Wrapper.lift(%0A%20%20%20%20%20%20%20%20lambda%20a%3A%20lambda%20b%3A%20lambda%20c%3A%20a%20%2B%20b%20*%20c%2C%0A%20%20%20%20%20%20%20%20Wrapper(1)%2C%0A%20%20%20%20%20%20%20%20Wrapper(2)%2C%0A%20%20%20%20%20%20%20%20Wrapper(3)%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20The%20List%20Applicative%0A%0A%20%20%20%20%20%20%20%20-%20%60pure%60%20should%20wrap%20the%20object%20in%20a%20list%2C%20in%20the%20sense%20that%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20%20%20%20%20List.pure(1)%20%3D%3E%20List(value%3D%5B1%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20%60apply%60%20should%20apply%20a%20list%20of%20functions%20to%20a%20list%20of%20values%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20you%20can%20think%20of%20this%20as%20cartesian%20product%2C%20concatenating%20the%20result%20of%20applying%20every%20function%20to%20every%20value%0A%0A%20%20%20%20%20%20%20%20The%20implementation%20is%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(A%2C%20Applicative%2C%20dataclass%2C%20product)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20List%5BA%5D(Applicative)%3A%0A%20%20%20%20%20%20%20%20value%3A%20list%5BA%5D%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20pure(cls%2C%20a%3A%20A)%20-%3E%20%22List%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(%5Ba%5D)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20apply(cls%2C%20fg%3A%20%22List%5BCallable%5B%5BA%5D%2C%20B%5D%5D%22%2C%20fa%3A%20%22List%5BA%5D%22)%20-%3E%20%22List%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(%5Bg(a)%20for%20g%2C%20a%20in%20product(fg.value%2C%20fa.value)%5D)%0A%20%20%20%20return%20(List%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%3E%20try%20with%20List%20below%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(List)%3A%0A%20%20%20%20List.apply(%0A%20%20%20%20%20%20%20%20List(%5Blambda%20a%3A%20a%20%2B%201%2C%20lambda%20a%3A%20a%20*%202%5D)%2C%0A%20%20%20%20%20%20%20%20List(%5B1%2C%202%5D)%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(List)%3A%0A%20%20%20%20List.lift(lambda%20a%3A%20lambda%20b%3A%20a%20%2B%20b%2C%20List(%5B1%2C%202%5D)%2C%20List(%5B3%2C%204%2C%205%5D))%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20The%20Maybe%20Applicative%0A%0A%20%20%20%20%20%20%20%20-%20%60pure%60%20should%20wrap%20the%20object%20in%20a%20Maybe%2C%20in%20the%20sense%20that%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20%20%20%20%20Maybe.pure(1)%20%20%20%20%3D%3E%20%22Just%201%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Maybe.pure(None)%20%3D%3E%20%22Nothing%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20%60apply%60%20should%20apply%20a%20function%20maybe%20exist%20to%20a%20value%20maybe%20exist%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20if%20the%20function%20is%20%60None%60%20or%20the%20value%20is%20%60None%60%2C%20simply%20returns%20%60None%60%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20else%20apply%20the%20function%20to%20the%20value%20and%20wrap%20the%20result%20in%20%60Just%60%0A%0A%20%20%20%20%20%20%20%20The%20implementation%20is%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(A%2C%20Applicative%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Maybe%5BA%5D(Applicative)%3A%0A%20%20%20%20%20%20%20%20value%3A%20None%20%7C%20A%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20pure(cls%2C%20a%3A%20A)%20-%3E%20%22Maybe%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(a)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20apply(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fg%3A%20%22Maybe%5BCallable%5B%5BA%5D%2C%20B%5D%5D%22%2C%20fa%3A%20%22Maybe%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Maybe%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fg.value%20is%20None%20or%20fa.value%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(None)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(fg.value(fa.value))%0A%0A%20%20%20%20%20%20%20%20def%20__repr__(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%22Nothing%22%20if%20self.value%20is%20None%20else%20f%22Just(%7Bself.value!r%7D)%22%0A%20%20%20%20return%20(Maybe%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%3E%20try%20with%20Maybe%20below%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Maybe)%3A%0A%20%20%20%20Maybe.lift(%0A%20%20%20%20%20%20%20%20lambda%20a%3A%20lambda%20b%3A%20a%20%2B%20b%2C%0A%20%20%20%20%20%20%20%20Maybe(1)%2C%0A%20%20%20%20%20%20%20%20Maybe(2)%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Maybe)%3A%0A%20%20%20%20Maybe.lift(%0A%20%20%20%20%20%20%20%20lambda%20a%3A%20lambda%20b%3A%20None%2C%0A%20%20%20%20%20%20%20%20Maybe(1)%2C%0A%20%20%20%20%20%20%20%20Maybe(2)%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20The%20Either%20Applicative%0A%0A%20%20%20%20%20%20%20%20-%20%60pure%60%20should%20wrap%20the%20object%20in%20%60Right%60%2C%20in%20the%20sense%20that%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20%20%20%20%20Either.pure(1)%20%3D%3E%20Right(1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20%60apply%60%20should%20apply%20a%20function%20that%20is%20either%20on%20Left%20or%20Right%20to%20a%20value%20that%20is%20either%20on%20Left%20or%20Right%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20if%20the%20function%20is%20%60Left%60%2C%20simply%20returns%20the%20%60Left%60%20of%20the%20function%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20else%20%60fmap%60%20the%20%60Right%60%20of%20the%20function%20to%20the%20value%0A%0A%20%20%20%20%20%20%20%20The%20implementation%20is%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(A%2C%20Applicative%2C%20B%2C%20Callable%2C%20Union%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Either%5BA%5D(Applicative)%3A%0A%20%20%20%20%20%20%20%20left%3A%20A%20%3D%20None%0A%20%20%20%20%20%20%20%20right%3A%20A%20%3D%20None%0A%0A%20%20%20%20%20%20%20%20def%20__post_init__(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(self.left%20is%20not%20None%20and%20self.right%20is%20not%20None)%20or%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.left%20is%20None%20and%20self.right%20is%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20msg%20%3D%20%22Provide%20either%20the%20value%20of%20the%20left%20or%20the%20value%20of%20the%20right.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20TypeError(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20msg%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20pure(cls%2C%20a%3A%20A)%20-%3E%20%22Either%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(right%3Da)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20apply(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fg%3A%20%22Either%5BCallable%5B%5BA%5D%2C%20B%5D%5D%22%2C%20fa%3A%20%22Either%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Either%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fg.left%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(left%3Dfg.left)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.fmap(fg.right%2C%20fa)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20fmap(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%3A%20%22Either%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20Union%5B%22Either%5BA%5D%22%2C%20%22Either%5BB%5D%22%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fa.left%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(left%3Dfa.left)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(right%3Dg(fa.right))%0A%0A%20%20%20%20%20%20%20%20def%20__repr__(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20self.left%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20f%22Left(%7Bself.left!r%7D)%22%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20f%22Right(%7Bself.right!r%7D)%22%0A%20%20%20%20return%20(Either%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%3E%20try%20with%20%60Either%60%20below%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Either)%3A%0A%20%20%20%20Either.apply(Either(left%3DTypeError(%22Parse%20Error%22))%2C%20Either(right%3D2))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Either)%3A%0A%20%20%20%20Either.apply(%0A%20%20%20%20%20%20%20%20Either(right%3Dlambda%20x%3A%20x%20%2B%201)%2C%20Either(left%3DTypeError(%22Parse%20Error%22))%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Either)%3A%0A%20%20%20%20Either.apply(Either(right%3Dlambda%20x%3A%20x%20%2B%201)%2C%20Either(right%3D1))%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Collect%20the%20list%20of%20response%20with%20sequenceL%0A%0A%20%20%20%20%20%20%20%20One%20often%20wants%20to%20execute%20a%20list%20of%20commands%20and%20collect%20the%20list%20of%20their%20response%2C%20and%20we%20can%20define%20a%20function%20%60sequenceL%60%20for%20this%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%0A%20%20%20%20%20%20%20%20In%20a%20further%20notebook%20about%20%60Traversable%60%2C%20we%20will%20have%20a%20more%20generic%20%60sequence%60%20that%20execute%20a%20**sequence**%20of%20commands%20and%20collect%20the%20**sequence**%20of%20their%20response%2C%20which%20is%20not%20limited%20to%20%60list%60.%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20sequenceL(cls%2C%20fas%3A%20list%5B%22Applicative%5BA%5D%22%5D)%20-%3E%20%22Applicative%5Blist%5BA%5D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20fas%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.pure(%5B%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.apply(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls.fmap(lambda%20v%3A%20lambda%20vs%3A%20%5Bv%5D%20%2B%20vs%2C%20fas%5B0%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls.sequenceL(fas%5B1%3A%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20Let's%20try%20%60sequenceL%60%20with%20the%20instances.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Wrapper)%3A%0A%20%20%20%20Wrapper.sequenceL(%5BWrapper(1)%2C%20Wrapper(2)%2C%20Wrapper(3)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20attention%0A%20%20%20%20%20%20%20%20For%20the%20%60Maybe%60%20Applicative%2C%20the%20presence%20of%20any%20%60Nothing%60%20causes%20the%20entire%20computation%20to%20return%20Nothing.%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Maybe)%3A%0A%20%20%20%20Maybe.sequenceL(%5BMaybe(1)%2C%20Maybe(2)%2C%20Maybe(None)%2C%20Maybe(3)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22The%20result%20of%20%60sequenceL%60%20for%20%60List%20Applicative%60%20%20is%20the%20Cartesian%20product%20of%20the%20input%20lists%2C%20yielding%20all%20possible%20ordered%20combinations%20of%20elements%20from%20each%20list.%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(List)%3A%0A%20%20%20%20List.sequenceL(%5BList(%5B1%2C%202%5D)%2C%20List(%5B3%5D)%2C%20List(%5B5%2C%206%2C%207%5D)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Applicative%20laws%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%20%7C%20id%20and%20compose%0A%0A%20%20%20%20%20%20%20%20Remember%20that%0A%0A%20%20%20%20%20%20%20%20-%20%60id%20%3D%20lambda%20x%3A%20x%60%0A%20%20%20%20%20%20%20%20-%20%60compose%20%3D%20lambda%20f%3A%20lambda%20g%3A%20lambda%20x%3A%20f(g(x))%60%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20Traditionally%2C%20there%20are%20four%20laws%20that%20%60Applicative%60%20instances%20should%20satisfy.%20In%20some%20sense%2C%20they%20are%20all%20concerned%20with%20making%20sure%20that%20%60pure%60%20deserves%20its%20name%3A%0A%0A%20%20%20%20%20%20%20%20-%20The%20identity%20law%3A%0A%20%20%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%20%20%23%20fa%3A%20Applicative%5BA%5D%0A%20%20%20%20%20%20%20%20%20%20apply(pure(id)%2C%20fa)%20%3D%20fa%0A%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20-%20Homomorphism%3A%0A%20%20%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%20%20%23%20a%3A%20A%0A%20%20%20%20%20%20%20%20%20%20%23%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%0A%20%20%20%20%20%20%20%20%20%20apply(pure(g)%2C%20pure(a))%20%3D%20pure(g(a))%0A%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20%20%20Intuitively%2C%20applying%20a%20non-effectful%20function%20to%20a%20non-effectful%20argument%20in%20an%20effectful%20context%20is%20the%20same%20as%20just%20applying%20the%20function%20to%20the%20argument%20and%20then%20injecting%20the%20result%20into%20the%20context%20with%20pure.%0A%20%20%20%20%20%20%20%20-%20Interchange%3A%0A%20%20%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%20%20%23%20a%3A%20A%0A%20%20%20%20%20%20%20%20%20%20%23%20fg%3A%20Applicative%5BCallable%5B%5BA%5D%2C%20B%5D%5D%0A%20%20%20%20%20%20%20%20%20%20apply(fg%2C%20pure(a))%20%3D%20apply(pure(lambda%20g%3A%20g(a))%2C%20fg)%0A%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20%20%20Intuitively%2C%20this%20says%20that%20when%20evaluating%20the%20application%20of%20an%20effectful%20function%20to%20a%20pure%20argument%2C%20the%20order%20in%20which%20we%20evaluate%20the%20function%20and%20its%20argument%20doesn't%20matter.%0A%20%20%20%20%20%20%20%20-%20Composition%3A%0A%20%20%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%20%20%23%20fg%3A%20Applicative%5BCallable%5B%5BB%5D%2C%20C%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%23%20fh%3A%20Applicative%5BCallable%5B%5BA%5D%2C%20B%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%23%20fa%3A%20Applicative%5BA%5D%0A%20%20%20%20%20%20%20%20%20%20apply(fg%2C%20apply(fh%2C%20fa))%20%3D%20lift(compose%2C%20fg%2C%20fh%2C%20fa)%0A%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20%20%20This%20one%20is%20the%20trickiest%20law%20to%20gain%20intuition%20for.%20In%20some%20sense%20it%20is%20expressing%20a%20sort%20of%20associativity%20property%20of%20%60apply%60.%0A%0A%20%20%20%20%20%20%20%20We%20can%20add%204%20helper%20functions%20to%20%60Applicative%60%20to%20check%20whether%20an%20instance%20respects%20the%20laws%20or%20not%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%40dataclass%0A%20%20%20%20%20%20%20%20class%20Applicative%5BA%5D(Functor%2C%20ABC)%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20check_identity(cls%2C%20fa%3A%20%22Applicative%5BA%5D%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20cls.lift(id%2C%20fa)%20!%3D%20fa%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(%22Instance%20violates%20identity%20law%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20check_homomorphism(cls%2C%20a%3A%20A%2C%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20cls.lift(f%2C%20cls.pure(a))%20!%3D%20cls.pure(f(a))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(%22Instance%20violates%20homomorphism%20law%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20check_interchange(cls%2C%20a%3A%20A%2C%20fg%3A%20%22Applicative%5BCallable%5B%5BA%5D%2C%20B%5D%5D%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20cls.apply(fg%2C%20cls.pure(a))%20!%3D%20cls.lift(lambda%20g%3A%20g(a)%2C%20fg)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(%22Instance%20violates%20interchange%20law%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20check_composition(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fg%3A%20%22Applicative%5BCallable%5B%5BB%5D%2C%20C%5D%5D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fh%3A%20%22Applicative%5BCallable%5B%5BA%5D%2C%20B%5D%5D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fa%3A%20%22Applicative%5BA%5D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20cls.apply(fg%2C%20cls.apply(fh%2C%20fa))%20!%3D%20cls.lift(compose%2C%20fg%2C%20fh%2C%20fa)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(%22Instance%20violates%20composition%20law%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20%3E%20Try%20to%20validate%20applicative%20laws%20below%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20id%20%3D%20lambda%20x%3A%20x%0A%20%20%20%20compose%20%3D%20lambda%20f%3A%20lambda%20g%3A%20lambda%20x%3A%20f(g(x))%0A%20%20%20%20const%20%3D%20lambda%20a%3A%20lambda%20_%3A%20a%0A%20%20%20%20return%20compose%2C%20const%2C%20id%0A%0A%0A%40app.cell%0Adef%20_(List%2C%20Wrapper)%3A%0A%20%20%20%20print(%22Checking%20Wrapper%22)%0A%20%20%20%20print(Wrapper.check_identity(Wrapper.pure(1)))%0A%20%20%20%20print(Wrapper.check_homomorphism(1%2C%20lambda%20x%3A%20x%20%2B%201))%0A%20%20%20%20print(Wrapper.check_interchange(1%2C%20Wrapper.pure(lambda%20x%3A%20x%20%2B%201)))%0A%20%20%20%20print(%0A%20%20%20%20%20%20%20%20Wrapper.check_composition(%0A%20%20%20%20%20%20%20%20%20%20%20%20Wrapper.pure(lambda%20x%3A%20x%20*%202)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20Wrapper.pure(lambda%20x%3A%20x%20%2B%200.1)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20Wrapper.pure(1)%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%0A%20%20%20%20print(%22%5CnChecking%20List%22)%0A%20%20%20%20print(List.check_identity(List.pure(1)))%0A%20%20%20%20print(List.check_homomorphism(1%2C%20lambda%20x%3A%20x%20%2B%201))%0A%20%20%20%20print(List.check_interchange(1%2C%20List.pure(lambda%20x%3A%20x%20%2B%201)))%0A%20%20%20%20print(%0A%20%20%20%20%20%20%20%20List.check_composition(%0A%20%20%20%20%20%20%20%20%20%20%20%20List.pure(lambda%20x%3A%20x%20*%202)%2C%20List.pure(lambda%20x%3A%20x%20%2B%200.1)%2C%20List.pure(1)%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Utility%20functions%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20attention%20%7C%20using%20%60fmap%60%0A%20%20%20%20%20%20%20%20%60fmap%60%20is%20defined%20automatically%20using%20%60pure%60%20and%20%60apply%60%2C%20so%20you%20can%20use%20%60fmap%60%20with%20any%20%60Applicative%60%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%40dataclass%0A%20%20%20%20%20%20%20%20class%20Applicative%5BA%5D(Functor%2C%20ABC)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20skip(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fa%3A%20%22Applicative%5BA%5D%22%2C%20fb%3A%20%22Applicative%5BB%5D%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%20-%3E%20%22Applicative%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20'''%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Sequences%20the%20effects%20of%20two%20Applicative%20computations%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20but%20discards%20the%20result%20of%20the%20first.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20'''%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.apply(cls.const(fa%2C%20id)%2C%20fb)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20keep(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fa%3A%20%22Applicative%5BA%5D%22%2C%20fb%3A%20%22Applicative%5BB%5D%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%20-%3E%20%22Applicative%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20'''%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Sequences%20the%20effects%20of%20two%20Applicative%20computations%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20but%20discard%20the%20result%20of%20the%20second.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20'''%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.lift(const%2C%20fa%2C%20fb)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20revapp(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fa%3A%20%22Applicative%5BA%5D%22%2C%20fg%3A%20%22Applicative%5BCallable%5B%5BA%5D%2C%20%5BB%5D%5D%5D%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%20-%3E%20%22Applicative%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20'''%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20The%20first%20computation%20produces%20values%20which%20are%20provided%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20as%20input%20to%20the%20function(s)%20produced%20by%20the%20second%20computation.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20'''%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.lift(lambda%20a%3A%20lambda%20f%3A%20f(a)%2C%20fa%2C%20fg)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20%60skip%60%20sequences%20the%20effects%20of%20two%20Applicative%20computations%2C%20but%20**discards%20the%20result%20of%20the%20first**.%20For%20example%2C%20if%20%60m1%60%20and%20%60m2%60%20are%20instances%20of%20type%20%60Maybe%5BInt%5D%60%2C%20then%20%60Maybe.skip(m1%2C%20m2)%60%20is%20%60Nothing%60%20whenever%20either%20%60m1%60%20or%20%60m2%60%20is%20%60Nothing%60%3B%20but%20if%20not%2C%20it%20will%20have%20the%20same%20value%20as%20%60m2%60.%0A%20%20%20%20%20%20%20%20-%20Likewise%2C%20%60keep%60%20sequences%20the%20effects%20of%20two%20computations%2C%20but%20**keeps%20only%20the%20result%20of%20the%20first**.%0A%20%20%20%20%20%20%20%20-%20%60revapp%60%20is%20similar%20to%20%60apply%60%2C%20but%20where%20the%20first%20computation%20produces%20value(s)%20which%20are%20provided%20as%20input%20to%20the%20function(s)%20produced%20by%20the%20second%20computation.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%20%7C%20Exercise%0A%20%20%20%20%20%20%20%20Try%20to%20use%20utility%20functions%20with%20different%20instances%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Formal%20implementation%20of%20Applicative%0A%0A%20%20%20%20%20%20%20%20Now%2C%20we%20can%20give%20the%20formal%20implementation%20of%20%60Applicative%60%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20ABC%2C%0A%20%20%20%20B%2C%0A%20%20%20%20Callable%2C%0A%20%20%20%20Functor%2C%0A%20%20%20%20abstractmethod%2C%0A%20%20%20%20compose%2C%0A%20%20%20%20const%2C%0A%20%20%20%20dataclass%2C%0A%20%20%20%20id%2C%0A)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Applicative%5BA%5D(Functor%2C%20ABC)%3A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20def%20pure(cls%2C%20a%3A%20A)%20-%3E%20%22Applicative%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22Lift%20a%20value%20into%20the%20Structure.%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20msg%20%3D%20%22Subclasses%20must%20implement%20pure%22%0A%20%20%20%20%20%20%20%20%20%20%20%20raise%20NotImplementedError(msg)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20def%20apply(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fg%3A%20%22Applicative%5BCallable%5B%5BA%5D%2C%20B%5D%5D%22%2C%20fa%3A%20%22Applicative%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Applicative%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22Sequential%20application.%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20msg%20%3D%20%22Subclasses%20must%20implement%20apply%22%0A%20%20%20%20%20%20%20%20%20%20%20%20raise%20NotImplementedError(msg)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20lift(cls%2C%20f%3A%20Callable%2C%20*args%3A%20%22Applicative%22)%20-%3E%20%22Applicative%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22Lift%20a%20function%20of%20arbitrary%20arity%20to%20work%20with%20values%20in%20applicative%20context.%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20curr%20%3D%20cls.pure(f)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20curr%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20arg%20in%20args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20curr%20%3D%20cls.apply(curr%2C%20arg)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20curr%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20fmap(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%3A%20%22Applicative%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Applicative%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.lift(f%2C%20fa)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20sequenceL(cls%2C%20fas%3A%20list%5B%22Applicative%5BA%5D%22%5D)%20-%3E%20%22Applicative%5Blist%5BA%5D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Execute%20a%20list%20of%20commands%20and%20collect%20the%20list%20of%20their%20response.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20fas%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.pure(%5B%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.apply(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls.fmap(lambda%20v%3A%20lambda%20vs%3A%20%5Bv%2C%20*vs%5D%2C%20fas%5B0%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls.sequenceL(fas%5B1%3A%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20skip(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fa%3A%20%22Applicative%5BA%5D%22%2C%20fb%3A%20%22Applicative%5BB%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Applicative%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Sequences%20the%20effects%20of%20two%20Applicative%20computations%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20but%20discards%20the%20result%20of%20the%20first.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.apply(cls.const(fa%2C%20id)%2C%20fb)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20keep(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fa%3A%20%22Applicative%5BA%5D%22%2C%20fb%3A%20%22Applicative%5BB%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Applicative%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Sequences%20the%20effects%20of%20two%20Applicative%20computations%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20but%20discard%20the%20result%20of%20the%20second.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.lift(const%2C%20fa%2C%20fb)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20revapp(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fa%3A%20%22Applicative%5BA%5D%22%2C%20fg%3A%20%22Applicative%5BCallable%5B%5BA%5D%2C%20%5BB%5D%5D%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Applicative%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20first%20computation%20produces%20values%20which%20are%20provided%0A%20%20%20%20%20%20%20%20%20%20%20%20as%20input%20to%20the%20function(s)%20produced%20by%20the%20second%20computation.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.lift(lambda%20a%3A%20lambda%20f%3A%20f(a)%2C%20fa%2C%20fg)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20check_identity(cls%2C%20fa%3A%20%22Applicative%5BA%5D%22)%20-%3E%20bool%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20cls.lift(id%2C%20fa)%20!%3D%20fa%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20msg%20%3D%20%22Instance%20violates%20identity%20law%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(msg)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20check_homomorphism(cls%2C%20a%3A%20A%2C%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D)%20-%3E%20bool%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20cls.lift(f%2C%20cls.pure(a))%20!%3D%20cls.pure(f(a))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20msg%20%3D%20%22Instance%20violates%20homomorphism%20law%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(msg)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20check_interchange(cls%2C%20a%3A%20A%2C%20fg%3A%20%22Applicative%5BCallable%5B%5BA%5D%2C%20B%5D%5D%22)%20-%3E%20bool%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20cls.apply(fg%2C%20cls.pure(a))%20!%3D%20cls.lift(lambda%20g%3A%20g(a)%2C%20fg)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20msg%20%3D%20%22Instance%20violates%20interchange%20law%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(msg)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20check_composition(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fg%3A%20%22Applicative%5BCallable%5B%5BB%5D%2C%20C%5D%5D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fh%3A%20%22Applicative%5BCallable%5B%5BA%5D%2C%20B%5D%5D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fa%3A%20%22Applicative%5BA%5D%22%2C%0A%20%20%20%20%20%20%20%20)%20-%3E%20bool%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20cls.apply(fg%2C%20cls.apply(fh%2C%20fa))%20!%3D%20cls.lift(compose%2C%20fg%2C%20fh%2C%20fa)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20msg%20%3D%20%22Instance%20violates%20composition%20law%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(msg)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%20%20%20return%20(Applicative%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Effectful%20programming%0A%0A%20%20%20%20%20%20%20%20Our%20original%20motivation%20for%20applicatives%20was%20the%20desire%20to%20generalise%20the%20idea%20of%20mapping%20to%20functions%20with%20multiple%20arguments.%20This%20is%20a%20valid%20interpretation%20of%20the%20concept%20of%20applicatives%2C%20but%20from%20the%20three%20instances%20we%20have%20seen%20it%20becomes%20clear%20that%20there%20is%20also%20another%2C%20more%20abstract%20view.%0A%0A%20%20%20%20%20%20%20%20%20The%20arguments%20are%20no%20longer%20just%20plain%20values%20but%20may%20also%20have%20effects%2C%20such%20as%20the%20possibility%20of%20failure%2C%20having%20many%20ways%20to%20succeed%2C%20or%20performing%20input%2Foutput%20actions.%20In%20this%20manner%2C%20applicative%20functors%20can%20also%20be%20viewed%20as%20abstracting%20the%20idea%20of%20**applying%20pure%20functions%20to%20effectful%20arguments**%2C%20with%20the%20precise%20form%20of%20effects%20that%20are%20permitted%20depending%20on%20the%20nature%20of%20the%20underlying%20functor.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20The%20IO%20Applicative%0A%0A%20%20%20%20%20%20%20%20We%20will%20try%20to%20define%20an%20%60IO%60%20applicative%20here.%0A%0A%20%20%20%20%20%20%20%20As%20before%2C%20we%20first%20abstract%20how%20%60pure%60%20and%20%60apply%60%20should%20function.%0A%0A%20%20%20%20%20%20%20%20-%20%60pure%60%20should%20wrap%20the%20object%20in%20an%20IO%20action%2C%20and%20make%20the%20object%20*callable*%20if%20it's%20not%20because%20we%20want%20to%20perform%20the%20action%20later%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20%20%20%20%20IO.pure(1)%20%3D%3E%20IO(effect%3Dlambda%3A%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20IO.pure(f)%20%3D%3E%20IO(effect%3Df)%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20%60apply%60%20should%20perform%20an%20action%20that%20produces%20a%20value%2C%20then%20apply%20the%20function%20with%20the%20value%0A%0A%20%20%20%20%20%20%20%20The%20implementation%20is%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Applicative%2C%20Callable%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20IO(Applicative)%3A%0A%20%20%20%20%20%20%20%20effect%3A%20Callable%0A%0A%20%20%20%20%20%20%20%20def%20__call__(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20self.effect()%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20pure(cls%2C%20a)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(a)%20if%20isinstance(a%2C%20Callable)%20else%20IO(lambda%3A%20a)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20apply(cls%2C%20fg%2C%20fa)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.pure(fg.effect(fa.effect()))%0A%20%20%20%20return%20(IO%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22For%20example%2C%20a%20function%20that%20reads%20a%20given%20number%20of%20lines%20from%20the%20keyboard%20can%20be%20defined%20in%20applicative%20style%20as%20follows%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(IO)%3A%0A%20%20%20%20def%20get_chars(n%3A%20int%20%3D%203)%3A%0A%20%20%20%20%20%20%20%20return%20IO.sequenceL(%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20IO.pure(input(f%22input%20the%20%7Bi%7Dth%20str%22))%20for%20i%20in%20range(1%2C%20n%20%2B%201)%0A%20%20%20%20%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20%23%20get_chars()()%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%23%20From%20the%20perspective%20of%20category%20theory%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Lax%20Monoidal%20Functor%0A%0A%20%20%20%20%20%20%20%20An%20alternative%2C%20equivalent%20formulation%20of%20%60Applicative%60%20is%20given%20by%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ABC%2C%20Functor%2C%20abstractmethod%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Monoidal%5BA%5D(Functor%2C%20ABC)%3A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20def%20unit(cls)%20-%3E%20%22Monoidal%5BTuple%5B()%5D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20pass%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20def%20tensor(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20this%3A%20%22Monoidal%5BA%5D%22%2C%20other%3A%20%22Monoidal%5BB%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Monoidal%5BTuple%5BA%2C%20B%5D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20pass%0A%20%20%20%20return%20(Monoidal%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Intuitively%2C%20this%20states%20that%20a%20*monoidal%20functor*%20is%20one%20which%20has%20some%20sort%20of%20%22default%20shape%22%20and%20which%20supports%20some%20sort%20of%20%22combining%22%20operation.%0A%0A%20%20%20%20%20%20%20%20-%20%60unit%60%20provides%20the%20identity%20element%0A%20%20%20%20%20%20%20%20-%20%60tensor%60%20combines%20two%20contexts%20into%20a%20product%20context%0A%0A%20%20%20%20%20%20%20%20More%20technically%2C%20the%20idea%20is%20that%20%60monoidal%20functor%60%20preserves%20the%20%22monoidal%20structure%22%20given%20by%20the%20pairing%20constructor%20%60(%2C)%60%20and%20unit%20type%20%60()%60.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Furthermore%2C%20to%20deserve%20the%20name%20%22monoidal%22%2C%20instances%20of%20Monoidal%20ought%20to%20satisfy%20the%20following%20laws%2C%20which%20seem%20much%20more%20straightforward%20than%20the%20traditional%20Applicative%20laws%3A%0A%0A%20%20%20%20%20%20%20%20-%20Left%20identity%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60tensor(unit%2C%20v)%20%E2%89%85%20v%60%0A%0A%20%20%20%20%20%20%20%20-%20Right%20identity%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60tensor(u%2C%20unit)%20%E2%89%85%20u%60%0A%0A%20%20%20%20%20%20%20%20-%20Associativity%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60tensor(u%2C%20tensor(v%2C%20w))%20%E2%89%85%20tensor(tensor(u%2C%20v)%2C%20w)%60%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%E2%89%85%20indicates%20isomorphism%0A%0A%20%20%20%20%20%20%20%20%60%E2%89%85%60%20refers%20to%20*isomorphism*%20rather%20than%20equality.%0A%0A%20%20%20%20%20%20%20%20In%20particular%20we%20consider%20%60(x%2C%20())%20%E2%89%85%20x%20%E2%89%85%20(()%2C%20x)%60%20and%20%60((x%2C%20y)%2C%20z)%20%E2%89%85%20(x%2C%20(y%2C%20z))%60%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Mutual%20definability%20of%20Monoidal%20and%20Applicative%0A%0A%20%20%20%20%20%20%20%20We%20can%20implement%20%60pure%60%20and%20%60apply%60%20in%20terms%20of%20%60unit%60%20and%20%60tensor%60%2C%20and%20vice%20versa.%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20pure(a)%20%3D%20fmap((lambda%20_%3A%20a)%2C%20unit)%0A%20%20%20%20%20%20%20%20apply(fg%2C%20fa)%20%3D%20fmap((lambda%20pair%3A%20pair%5B0%5D(pair%5B1%5D))%2C%20tensor(fg%2C%20fa))%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20unit()%20%3D%20pure(())%0A%20%20%20%20%20%20%20%20tensor(fa%2C%20fb)%20%3D%20lift(lambda%20fa%3A%20lambda%20fb%3A%20(fa%2C%20fb)%2C%20fa%2C%20fb)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Instance%3A%20ListMonoidal%0A%0A%20%20%20%20%20%20%20%20-%20%60unit%60%20should%20simply%20return%20a%20empty%20tuple%20wrapper%20in%20a%20list%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20%20%20%20%20ListMonoidal.unit()%20%3D%3E%20%5B()%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20%60tensor%60%20should%20return%20the%20*cartesian%20product*%20of%20the%20items%20of%202%20ListMonoidal%20instances%0A%0A%20%20%20%20%20%20%20%20The%20implementation%20is%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(A%2C%20B%2C%20Callable%2C%20Monoidal%2C%20dataclass%2C%20product)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20ListMonoidal%5BA%5D(Monoidal)%3A%0A%20%20%20%20%20%20%20%20items%3A%20list%5BA%5D%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20unit(cls)%20-%3E%20%22ListMonoidal%5BTuple%5B()%5D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(%5B()%5D)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20tensor(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20this%3A%20%22ListMonoidal%5BA%5D%22%2C%20other%3A%20%22ListMonoidal%5BB%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22ListMonoidal%5BTuple%5BA%2C%20B%5D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(list(product(this.items%2C%20other.items)))%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20fmap(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20ma%3A%20%22ListMonoidal%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22ListMonoidal%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(%5Bf(a)%20for%20a%20in%20ma.items%5D)%0A%20%20%20%20return%20(ListMonoidal%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%3E%20try%20with%20%60ListMonoidal%60%20below%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ListMonoidal)%3A%0A%20%20%20%20xs%20%3D%20ListMonoidal(%5B1%2C%202%5D)%0A%20%20%20%20ys%20%3D%20ListMonoidal(%5B%22a%22%2C%20%22b%22%5D)%0A%20%20%20%20ListMonoidal.tensor(xs%2C%20ys)%0A%20%20%20%20return%20xs%2C%20ys%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22and%20we%20can%20prove%20that%20%60tensor(fa%2C%20fb)%20%3D%20lift(lambda%20fa%3A%20lambda%20fb%3A%20(fa%2C%20fb)%2C%20fa%2C%20fb)%60%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(List%2C%20xs%2C%20ys)%3A%0A%20%20%20%20List.lift(lambda%20fa%3A%20lambda%20fb%3A%20(fa%2C%20fb)%2C%20List(xs.items)%2C%20List(ys.items))%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(ABC%2C%20B%2C%20Callable%2C%20abstractmethod%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Functor%5BA%5D(ABC)%3A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20def%20fmap(cls%2C%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%3A%20%22Functor%5BA%5D%22)%20-%3E%20%22Functor%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20msg%20%3D%20%22Subclasses%20must%20implement%20fmap%22%0A%20%20%20%20%20%20%20%20%20%20%20%20raise%20NotImplementedError(msg)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20const(cls%2C%20a%3A%20%22Functor%5BA%5D%22%2C%20b%3A%20B)%20-%3E%20%22Functor%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.fmap(lambda%20_%3A%20b%2C%20a)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20void(cls%2C%20a%3A%20%22Functor%5BA%5D%22)%20-%3E%20%22Functor%5BNone%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.const_fmap(a%2C%20None)%0A%20%20%20%20return%20(Functor%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20from%20abc%20import%20ABC%2C%20abstractmethod%0A%20%20%20%20from%20collections.abc%20import%20Callable%0A%20%20%20%20from%20dataclasses%20import%20dataclass%0A%20%20%20%20from%20typing%20import%20TypeVar%2C%20Union%0A%20%20%20%20return%20ABC%2C%20Callable%2C%20TypeVar%2C%20Union%2C%20abstractmethod%2C%20dataclass%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20from%20itertools%20import%20product%0A%20%20%20%20return%20(product%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(TypeVar)%3A%0A%20%20%20%20A%20%3D%20TypeVar(%22A%22)%0A%20%20%20%20B%20%3D%20TypeVar(%22B%22)%0A%20%20%20%20C%20%3D%20TypeVar(%22C%22)%0A%20%20%20%20return%20A%2C%20B%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20From%20Applicative%20to%20Alternative%0A%0A%20%20%20%20%20%20%20%20%23%23%20Abstracting%20Alternative%0A%0A%20%20%20%20%20%20%20%20In%20our%20studies%20so%20far%2C%20we%20saw%20that%20both%20%60Maybe%60%20and%20%60List%60%20can%20represent%20computations%20with%20a%20varying%20number%20of%20results.%0A%0A%20%20%20%20%20%20%20%20We%20use%20%60Maybe%60%20to%20indicate%20a%20computation%20can%20fail%20somehow%20and%20%60List%60%20for%20computations%20that%20can%20have%20many%20possible%20results.%20In%20both%20of%20these%20cases%2C%20one%20useful%20operation%20is%20amalgamating%20all%20possible%20results%20from%20multiple%20computations%20into%20a%20single%20computation.%0A%0A%20%20%20%20%20%20%20%20%60Alternative%60%20formalizes%20computations%20that%20support%3A%0A%0A%20%20%20%20%20%20%20%20-%20**Failure**%20(empty%20result)%0A%20%20%20%20%20%20%20%20-%20**Choice**%20(combination%20of%20results)%0A%20%20%20%20%20%20%20%20-%20**Repetition**%20(multiple%20results)%0A%0A%20%20%20%20%20%20%20%20It%20extends%20%60Applicative%60%20with%20monoidal%20structure%2C%20where%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%40dataclass%0A%20%20%20%20%20%20%20%20class%20Alternative%5BA%5D(Applicative%2C%20ABC)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20empty(cls)%20-%3E%20%22Alternative%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20'''Identity%20element%20for%20alternative%20computations'''%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20alt(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fa%3A%20%22Alternative%5BA%5D%22%2C%20fb%3A%20%22Alternative%5BA%5D%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%20-%3E%20%22Alternative%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20'''Binary%20operation%20combining%20computations'''%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20%60empty%60%20is%20the%20identity%20element%20(e.g.%2C%20%60Maybe(None)%60%2C%20%60List(%5B%5D)%60)%0A%20%20%20%20%20%20%20%20-%20%60alt%60%20is%20a%20combination%20operator%20(e.g.%2C%20%60Maybe%60%20fallback%2C%20list%20concatenation)%0A%0A%20%20%20%20%20%20%20%20%60empty%60%20and%20%60alt%60%20should%20satisfy%20the%20following%20**laws**%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%23%20Left%20identity%0A%20%20%20%20%20%20%20%20alt(empty%2C%20fa)%20%3D%3D%20fa%0A%20%20%20%20%20%20%20%20%23%20Right%20identity%0A%20%20%20%20%20%20%20%20alt(fa%2C%20empty)%20%3D%3D%20fa%0A%20%20%20%20%20%20%20%20%23%20Associativity%0A%20%20%20%20%20%20%20%20alt(fa%2C%20alt(fb%2C%20fc))%20%3D%3D%20alt(alt(fa%2C%20fb)%2C%20fc)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%0A%20%20%20%20%20%20%20%20Actually%2C%20%60Alternative%60%20is%20a%20*monoid*%20on%20%60Applicative%20Functors%60.%20We%20will%20talk%20about%20*monoid*%20and%20review%20these%20laws%20in%20the%20next%20notebook%20about%20%60Monads%60.%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20attention%20%7C%20minimal%20implementation%20requirement%0A%20%20%20%20%20%20%20%20-%20%60empty%60%0A%20%20%20%20%20%20%20%20-%20%60alt%60%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Instances%20of%20Alternative%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20The%20Maybe%20Alternative%0A%0A%20%20%20%20%20%20%20%20-%20%60empty%60%3A%20the%20identity%20element%20of%20%60Maybe%60%20is%20%60Maybe(None)%60%0A%20%20%20%20%20%20%20%20-%20%60alt%60%3A%20return%20the%20first%20element%20if%20it's%20not%20%60None%60%2C%20else%20return%20the%20second%20element%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Alternative%2C%20Maybe%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20AltMaybe%5BA%5D(Maybe%2C%20Alternative)%3A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20empty(cls)%20-%3E%20%22AltMaybe%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(None)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20alt(cls%2C%20fa%3A%20%22AltMaybe%5BA%5D%22%2C%20fb%3A%20%22AltMaybe%5BA%5D%22)%20-%3E%20%22AltMaybe%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fa.value%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(fa.value)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(fb.value)%0A%0A%20%20%20%20%20%20%20%20def%20__repr__(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%22Nothing%22%20if%20self.value%20is%20None%20else%20f%22Just(%7Bself.value!r%7D)%22%0A%20%20%20%20return%20(AltMaybe%2C)%0A%0A%0A%40app.cell%0Adef%20_(AltMaybe)%3A%0A%20%20%20%20print(AltMaybe.empty())%0A%20%20%20%20print(AltMaybe.alt(AltMaybe(None)%2C%20AltMaybe(1)))%0A%20%20%20%20print(AltMaybe.alt(AltMaybe(None)%2C%20AltMaybe(None)))%0A%20%20%20%20print(AltMaybe.alt(AltMaybe(1)%2C%20AltMaybe(None)))%0A%20%20%20%20print(AltMaybe.alt(AltMaybe(1)%2C%20AltMaybe(2)))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(AltMaybe)%3A%0A%20%20%20%20print(AltMaybe.check_left_identity(AltMaybe(1)))%0A%20%20%20%20print(AltMaybe.check_right_identity(AltMaybe(1)))%0A%20%20%20%20print(AltMaybe.check_associativity(AltMaybe(1)%2C%20AltMaybe(2)%2C%20AltMaybe(None)))%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20The%20List%20Alternative%0A%0A%20%20%20%20%20%20%20%20-%20%60empty%60%3A%20the%20identity%20element%20of%20%60List%60%20is%20%60List(%5B%5D)%60%0A%20%20%20%20%20%20%20%20-%20%60alt%60%3A%20return%20the%20concatenation%20of%202%20input%20lists%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Alternative%2C%20List%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20AltList%5BA%5D(List%2C%20Alternative)%3A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20empty(cls)%20-%3E%20%22AltList%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(%5B%5D)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20alt(cls%2C%20fa%3A%20%22AltList%5BA%5D%22%2C%20fb%3A%20%22AltList%5BA%5D%22)%20-%3E%20%22AltList%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(fa.value%20%2B%20fb.value)%0A%20%20%20%20return%20(AltList%2C)%0A%0A%0A%40app.cell%0Adef%20_(AltList)%3A%0A%20%20%20%20print(AltList.empty())%0A%20%20%20%20print(AltList.alt(AltList(%5B1%2C%202%2C%203%5D)%2C%20AltList(%5B4%2C%205%5D)))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(AltList)%3A%0A%20%20%20%20AltList(%5B1%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(AltList)%3A%0A%20%20%20%20AltList(%5B1%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(AltList)%3A%0A%20%20%20%20print(AltList.check_left_identity(AltList(%5B1%2C%202%2C%203%5D)))%0A%20%20%20%20print(AltList.check_right_identity(AltList(%5B1%2C%202%2C%203%5D)))%0A%20%20%20%20print(%0A%20%20%20%20%20%20%20%20AltList.check_associativity(%0A%20%20%20%20%20%20%20%20%20%20%20%20AltList(%5B1%2C%202%5D)%2C%20AltList(%5B3%2C%204%2C%205%5D)%2C%20AltList(%5B6%5D)%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20some%20and%20many%0A%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%20%7C%20This%20section%20mainly%20refers%20to%0A%0A%20%20%20%20%20%20%20%20-%20https%3A%2F%2Fstackoverflow.com%2Fquestions%2F7671009%2Fsome-and-many-functions-from-the-alternative-type-class%2F7681283%237681283%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20First%20let's%20have%20a%20look%20at%20the%20implementation%20of%20%60some%60%20and%20%60many%60%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20some(cls%2C%20fa%3A%20%22Alternative%5BA%5D%22)%20-%3E%20%22Alternative%5Blist%5BA%5D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Short-circuit%20if%20input%20is%20empty%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fa%20%3D%3D%20cls.empty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.empty()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.apply(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls.fmap(lambda%20a%3A%20lambda%20b%3A%20%5Ba%5D%20%2B%20b%2C%20fa)%2C%20cls.many(fa)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20many(cls%2C%20fa%3A%20%22Alternative%5BA%5D%22)%20-%3E%20%22Alternative%5Blist%5BA%5D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Directly%20return%20empty%20list%20if%20input%20is%20empty%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fa%20%3D%3D%20cls.empty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.pure(%5B%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.alt(cls.some(fa)%2C%20cls.pure(%5B%5D))%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20So%20%60some%20f%60%20runs%20%60f%60%20once%2C%20then%20*many*%20times%2C%20and%20conses%20the%20results.%20%60many%20f%60%20runs%20f%20*some*%20times%2C%20or%20*alternatively*%20just%20returns%20the%20empty%20list.%0A%0A%20%20%20%20%20%20%20%20The%20idea%20is%20that%20they%20both%20run%20%60f%60%20as%20often%20as%20possible%20until%20it%20**fails**%2C%20collecting%20the%20results%20in%20a%20list.%20The%20difference%20is%20that%20%60some%20f%60%20immediately%20fails%20if%20%60f%60%20fails%2C%20while%20%60many%20f%60%20will%20still%20succeed%20and%20*return*%20the%20empty%20list%20in%20such%20a%20case.%20But%20what%20all%20this%20exactly%20means%20depends%20on%20how%20%60alt%60%20is%20defined.%0A%0A%20%20%20%20%20%20%20%20Let's%20see%20what%20it%20does%20for%20the%20instances%20%60AltMaybe%60%20and%20%60AltList%60.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22For%20%60AltMaybe%60.%20%60None%60%20means%20failure%2C%20so%20some%20%60None%60%20fails%20as%20well%20and%20evaluates%20to%20%60None%60%20while%20many%20%60None%60%20succeeds%20and%20evaluates%20to%20%60Just%20%5B%5D%60.%20Both%20%60some%20(Just%20())%60%20and%20%60many%20(Just%20())%60%20never%20return%2C%20because%20%60Just%20()%60%20never%20fails.%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(AltMaybe)%3A%0A%20%20%20%20print(AltMaybe.some(AltMaybe.empty()))%0A%20%20%20%20print(AltMaybe.many(AltMaybe.empty()))%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22For%20%60AltList%60%2C%20%60%5B%5D%60%20means%20failure%2C%20so%20%60some%20%5B%5D%60%20evaluates%20to%20%60%5B%5D%60%20(no%20answers)%20while%20%60many%20%5B%5D%60%20evaluates%20to%20%60%5B%5B%5D%5D%60%20(there's%20one%20answer%20and%20it%20is%20the%20empty%20list).%20Again%20%60some%20%5B()%5D%60%20and%20%60many%20%5B()%5D%60%20don't%20return.%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(AltList)%3A%0A%20%20%20%20print(AltList.some(AltList.empty()))%0A%20%20%20%20print(AltList.many(AltList.empty()))%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%23%23%20Formal%20implementation%20of%20Alternative%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ABC%2C%20Applicative%2C%20abstractmethod%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Alternative%5BA%5D(Applicative%2C%20ABC)%3A%0A%20%20%20%20%20%20%20%20%22%22%22A%20monoid%20on%20applicative%20functors.%22%22%22%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20def%20empty(cls)%20-%3E%20%22Alternative%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20msg%20%3D%20%22Subclasses%20must%20implement%20empty%22%0A%20%20%20%20%20%20%20%20%20%20%20%20raise%20NotImplementedError(msg)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20%40abstractmethod%0A%20%20%20%20%20%20%20%20def%20alt(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fa%3A%20%22Alternative%5BA%5D%22%2C%20fb%3A%20%22Alternative%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Alternative%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20msg%20%3D%20%22Subclasses%20must%20implement%20alt%22%0A%20%20%20%20%20%20%20%20%20%20%20%20raise%20NotImplementedError(msg)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20some(cls%2C%20fa%3A%20%22Alternative%5BA%5D%22)%20-%3E%20%22Alternative%5Blist%5BA%5D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Short-circuit%20if%20input%20is%20empty%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fa%20%3D%3D%20cls.empty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.empty()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.apply(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls.fmap(lambda%20a%3A%20lambda%20b%3A%20%5Ba%2C%20*b%5D%2C%20fa)%2C%20cls.many(fa)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20many(cls%2C%20fa%3A%20%22Alternative%5BA%5D%22)%20-%3E%20%22Alternative%5Blist%5BA%5D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Directly%20return%20empty%20list%20if%20input%20is%20empty%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fa%20%3D%3D%20cls.empty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.pure(%5B%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.alt(cls.some(fa)%2C%20cls.pure(%5B%5D))%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20check_left_identity(cls%2C%20fa%3A%20%22Alternative%5BA%5D%22)%20-%3E%20bool%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.alt(cls.empty()%2C%20fa)%20%3D%3D%20fa%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20check_right_identity(cls%2C%20fa%3A%20%22Alternative%5BA%5D%22)%20-%3E%20bool%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.alt(fa%2C%20cls.empty())%20%3D%3D%20fa%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20check_associativity(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fa%3A%20%22Alternative%5BA%5D%22%2C%20fb%3A%20%22Alternative%5BA%5D%22%2C%20fc%3A%20%22Alternative%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20bool%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.alt(fa%2C%20cls.alt(fb%2C%20fc))%20%3D%3D%20cls.alt(cls.alt(fa%2C%20fb)%2C%20fc)%0A%20%20%20%20return%20(Alternative%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%0A%0A%20%20%20%20%20%20%20%20We%20will%20explore%20more%20about%20%60Alternative%60%20in%20a%20future%20notebooks%20about%20%5BMonadic%20Parsing%5D(https%3A%2F%2Fwww.cambridge.org%2Fcore%2Fjournals%2Fjournal-of-functional-programming%2Farticle%2Fmonadic-parsing-in-haskell%2FE557DFCCE00E0D4B6ED02F3FB0466093)%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Further%20reading%0A%0A%20%20%20%20%20%20%20%20Notice%20that%20these%20reading%20sources%20are%20optional%20and%20non-trivial%0A%0A%20%20%20%20%20%20%20%20-%20%5BApplicaive%20Programming%20with%20Effects%5D(https%3A%2F%2Fwww.staff.city.ac.uk%2F~ross%2Fpapers%2FApplicative.html)%0A%20%20%20%20%20%20%20%20-%20%5BEquivalence%20of%20Applicative%20Functors%20and%0A%20%20%20%20%20%20%20%20Multifunctors%5D(https%3A%2F%2Farxiv.org%2Fpdf%2F2401.14286)%0A%20%20%20%20%20%20%20%20-%20%5BApplicative%20functor%5D(https%3A%2F%2Fwiki.haskell.org%2Findex.php%3Ftitle%3DApplicative_functor)%0A%20%20%20%20%20%20%20%20-%20%5BControl.Applicative%5D(https%3A%2F%2Fhackage.haskell.org%2Fpackage%2Fbase-4.21.0.0%2Fdocs%2FControl-Applicative.html%23t%3AApplicative)%0A%20%20%20%20%20%20%20%20-%20%5BTypeclassopedia%23Applicative%5D(https%3A%2F%2Fwiki.haskell.org%2Findex.php%3Ftitle%3DTypeclassopedia%23Applicative)%0A%20%20%20%20%20%20%20%20-%20%5BNotions%20of%20computation%20as%20monoids%5D(https%3A%2F%2Fwww.cambridge.org%2Fcore%2Fjournals%2Fjournal-of-functional-programming%2Farticle%2Fnotions-of-computation-as-monoids%2F70019FC0F2384270E9F41B9719042528)%0A%20%20%20%20%20%20%20%20-%20%5BFree%20Applicative%20Functors%5D(https%3A%2F%2Farxiv.org%2Fabs%2F1403.0749)%0A%20%20%20%20%20%20%20%20-%20%5BThe%20basics%20of%20applicative%20functors%2C%20put%20to%20practical%20work%5D(http%3A%2F%2Fwww.serpentine.com%2Fblog%2F2008%2F02%2F06%2Fthe-basics-of-applicative-functors-put-to-practical-work%2F)%0A%20%20%20%20%20%20%20%20-%20%5BAbstracting%20with%20Applicatives%5D(http%3A%2F%2Fcomonad.com%2Freader%2F2012%2Fabstracting-with-applicatives%2F)%0A%20%20%20%20%20%20%20%20-%20%5BStatic%20analysis%20with%20Applicatives%5D(https%3A%2F%2Fgergo.erdi.hu%2Fblog%2F2012-12-01-static_analysis_with_applicatives%2F)%0A%20%20%20%20%20%20%20%20-%20%5BExplaining%20Applicative%20functor%20in%20categorical%20terms%20-%20monoidal%20functors%5D(https%3A%2F%2Fcstheory.stackexchange.com%2Fquestions%2F12412%2Fexplaining-applicative-functor-in-categorical-terms-monoidal-functors)%0A%20%20%20%20%20%20%20%20-%20%5BApplicative%2C%20A%20Strong%20Lax%20Monoidal%20Functor%5D(https%3A%2F%2Fbeuke.org%2Fapplicative%2F)%0A%20%20%20%20%20%20%20%20-%20%5BApplicative%20Functors%5D(https%3A%2F%2Fbartoszmilewski.com%2F2017%2F02%2F06%2Fapplicative-functors%2F)%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A