Category Theory and Functors

import%20marimo%0A%0A__generated_with%20%3D%20%220.13.0%22%0Aapp%20%3D%20marimo.App(app_title%3D%22Category%20Theory%20and%20Functors%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Category%20Theory%20and%20Functors%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%20*%20Why%20%60length%60%20is%20a%20*functor*%20from%20the%20category%20of%20%60list%20concatenation%60%20to%20the%20category%20of%20%60integer%20addition%60%0A%20%20%20%20%20%20%20%20*%20How%20to%20*lift*%20an%20ordinary%20function%20into%20a%20specific%20*computational%20context*%0A%20%20%20%20%20%20%20%20*%20How%20to%20write%20an%20*adapter*%20between%20two%20categories%0A%0A%20%20%20%20%20%20%20%20In%20short%2C%20a%20mathematical%20functor%20is%20a%20**mapping**%20between%20two%20categories%20in%20category%20theory.%20In%20practice%2C%20a%20functor%20represents%20a%20type%20that%20can%20be%20mapped%20over.%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%20%7C%20Intuitions%20%0A%0A%20%20%20%20%20%20%20%20-%20A%20simple%20intuition%20is%20that%20a%20%60Functor%60%20represents%20a%20**container**%20of%20values%2C%20along%20with%20the%20ability%20to%20apply%20a%20function%20uniformly%20to%20every%20element%20in%20the%20container.%0A%20%20%20%20%20%20%20%20-%20Another%20intuition%20is%20that%20a%20%60Functor%60%20represents%20some%20sort%20of%20**computational%20context**.%0A%20%20%20%20%20%20%20%20-%20Mathematically%2C%20%60Functors%60%20generalize%20the%20idea%20of%20a%20container%20or%20a%20computational%20context.%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20We%20will%20start%20with%20intuition%2C%20introduce%20the%20basics%20of%20category%20theory%2C%20and%20then%20examine%20functors%20from%20a%20categorical%20perspective.%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.5%20%7C%20last%20modified%3A%202025-04-11%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Functor%20as%20a%20Computational%20Context%0A%0A%20%20%20%20%20%20%20%20A%20%5B**Functor**%5D(https%3A%2F%2Fwiki.haskell.org%2FFunctor)%20is%20an%20abstraction%20that%20represents%20a%20computational%20context%20with%20the%20ability%20to%20apply%20a%20function%20to%20every%20value%20inside%20it%20without%20altering%20the%20structure%20of%20the%20context%20itself.%20This%20enables%20transformations%20while%20preserving%20the%20shape%20of%20the%20data.%0A%0A%20%20%20%20%20%20%20%20To%20understand%20this%2C%20let's%20look%20at%20a%20simple%20example.%0A%0A%20%20%20%20%20%20%20%20%23%23%20%5BThe%20One-Way%20Wrapper%20Design%20Pattern%5D(http%3A%2F%2Fblog.sigfpe.com%2F2007%2F04%2Ftrivial-monad.html)%0A%0A%20%20%20%20%20%20%20%20Often%2C%20we%20need%20to%20wrap%20data%20in%20some%20kind%20of%20context.%20However%2C%20when%20performing%20operations%20on%20wrapped%20data%2C%20we%20typically%20have%20to%3A%0A%0A%20%20%20%20%20%20%20%201.%20Unwrap%20the%20data.%0A%20%20%20%20%20%20%20%202.%20Modify%20the%20unwrapped%20data.%0A%20%20%20%20%20%20%20%203.%20Rewrap%20the%20modified%20data.%0A%0A%20%20%20%20%20%20%20%20This%20process%20is%20tedious%20and%20inefficient.%20Instead%2C%20we%20want%20to%20wrap%20data%20**once**%20and%20apply%20functions%20directly%20to%20the%20wrapped%20data%20without%20unwrapping%20it.%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%20%7C%20Rules%20for%20a%20One-Way%20Wrapper%0A%0A%20%20%20%20%20%20%20%201.%20We%20can%20wrap%20values%2C%20but%20we%20cannot%20unwrap%20them.%0A%20%20%20%20%20%20%20%202.%20We%20should%20still%20be%20able%20to%20apply%20transformations%20to%20the%20wrapped%20data.%0A%20%20%20%20%20%20%20%203.%20Any%20operation%20that%20depends%20on%20wrapped%20data%20should%20itself%20return%20a%20wrapped%20result.%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20Let's%20define%20such%20a%20%60Wrapper%60%20class%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20from%20dataclasses%20import%20dataclass%0A%20%20%20%20%20%20%20%20from%20typing%20import%20TypeVar%0A%0A%20%20%20%20%20%20%20%20A%20%3D%20TypeVar(%22A%22)%0A%20%20%20%20%20%20%20%20B%20%3D%20TypeVar(%22B%22)%0A%0A%20%20%20%20%20%20%20%20%40dataclass%0A%20%20%20%20%20%20%20%20class%20Wrapper%5BA%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20value%3A%20A%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20Now%2C%20we%20can%20create%20an%20instance%20of%20wrapped%20data%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20wrapped%20%3D%20Wrapper(1)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20Mapping%20Functions%20Over%20Wrapped%20Data%0A%0A%20%20%20%20%20%20%20%20To%20modify%20wrapped%20data%20while%20keeping%20it%20wrapped%2C%20we%20define%20an%20%60fmap%60%20method%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_(B%2C%20Callable%2C%20Functor%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Wrapper%5BA%5D(Functor)%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%20fmap(cls%2C%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%3A%20%22Wrapper%5BA%5D%22)%20-%3E%20%22Wrapper%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20Wrapper(g(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(%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%0A%20%20%20%20%20%20%20%20To%20distinguish%20between%20regular%20types%20and%20functors%2C%20we%20use%20the%20prefix%20%60f%60%20to%20indicate%20%60Functor%60.%0A%0A%20%20%20%20%20%20%20%20For%20instance%2C%0A%0A%20%20%20%20%20%20%20%20-%20%60a%3A%20A%60%20is%20a%20regular%20variable%20of%20type%20%60A%60%0A%20%20%20%20%20%20%20%20-%20%60g%3A%20Callable%5B%5BA%5D%2C%20B%5D%60%20is%20a%20regular%20function%20from%20type%20%60A%60%20to%20%60B%60%0A%20%20%20%20%20%20%20%20-%20%60fa%3A%20Functor%5BA%5D%60%20is%20a%20*Functor*%20wrapping%20a%20value%20of%20type%20%60A%60%20%20%0A%20%20%20%20%20%20%20%20-%20%60fg%3A%20Functor%5BCallable%5B%5BA%5D%2C%20B%5D%5D%60%20is%20a%20*Functor*%20wrapping%20a%20function%20from%20type%20%60A%60%20to%20%60B%60%20%20%0A%0A%20%20%20%20%20%20%20%20and%20we%20will%20avoid%20using%20%60f%60%20to%20represent%20a%20function%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20%3E%20Try%20with%20Wrapper%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_(Wrapper%2C%20pp)%3A%0A%20%20%20%20wrapper%20%3D%20Wrapper(1)%0A%0A%20%20%20%20pp(Wrapper.fmap(lambda%20x%3A%20x%20%2B%201%2C%20wrapper))%0A%20%20%20%20pp(Wrapper.fmap(lambda%20x%3A%20%5Bx%5D%2C%20wrapper))%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(%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20We%20can%20analyze%20the%20type%20signature%20of%20%60fmap%60%20for%20%60Wrapper%60%3A%0A%0A%20%20%20%20%20%20%20%20*%20%60g%60%20is%20of%20type%20%60Callable%5B%5BA%5D%2C%20B%5D%60%0A%20%20%20%20%20%20%20%20*%20%60fa%60%20is%20of%20type%20%60Wrapper%5BA%5D%60%0A%20%20%20%20%20%20%20%20*%20The%20return%20value%20is%20of%20type%20%60Wrapper%5BB%5D%60%0A%0A%20%20%20%20%20%20%20%20Thus%2C%20in%20Python's%20type%20system%2C%20we%20can%20express%20the%20type%20signature%20of%20%60fmap%60%20as%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20fmap(g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%3A%20Wrapper%5BA%5D)%20-%3E%20Wrapper%5BB%5D%3A%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20Essentially%2C%20%60fmap%60%3A%0A%0A%20%20%20%20%20%20%20%201.%20Takes%20a%20function%20%60Callable%5B%5BA%5D%2C%20B%5D%60%20and%20a%20%60Wrapper%5BA%5D%60%20instance%20as%20input.%0A%20%20%20%20%20%20%20%202.%20Applies%20the%20function%20to%20the%20value%20inside%20the%20wrapper.%0A%20%20%20%20%20%20%20%203.%20Returns%20a%20new%20%60Wrapper%5BB%5D%60%20instance%20with%20the%20transformed%20value%2C%20leaving%20the%20original%20wrapper%20and%20its%20internal%20data%20unmodified.%0A%0A%20%20%20%20%20%20%20%20Now%2C%20let's%20examine%20%60list%60%20as%20a%20similar%20kind%20of%20wrapper.%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20The%20List%20Functor%0A%0A%20%20%20%20%20%20%20%20We%20can%20define%20a%20%60List%60%20class%20to%20represent%20a%20wrapped%20list%20that%20supports%20%60fmap%60%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_(B%2C%20Callable%2C%20Functor%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20List%5BA%5D(Functor)%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%20fmap(cls%2C%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%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%20List(%5Bg(x)%20for%20x%20in%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%2C%20pp)%3A%0A%20%20%20%20flist%20%3D%20List(%5B1%2C%202%2C%203%2C%204%5D)%0A%20%20%20%20pp(List.fmap(lambda%20x%3A%20x%20%2B%201%2C%20flist))%0A%20%20%20%20pp(List.fmap(lambda%20x%3A%20%5Bx%5D%2C%20flist))%0A%20%20%20%20return%20(flist%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Extracting%20the%20Type%20of%20%60fmap%60%0A%0A%20%20%20%20%20%20%20%20The%20type%20signature%20of%20%60fmap%60%20for%20%60List%60%20is%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20fmap(g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%3A%20List%5BA%5D)%20-%3E%20List%5BB%5D%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20Similarly%2C%20for%20%60Wrapper%60%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20fmap(g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%3A%20Wrapper%5BA%5D)%20-%3E%20Wrapper%5BB%5D%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20Both%20follow%20the%20same%20pattern%2C%20which%20we%20can%20generalize%20as%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20fmap(g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%3A%20Functor%5BA%5D)%20-%3E%20Functor%5BB%5D%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20where%20%60Functor%60%20can%20be%20%60Wrapper%60%2C%20%60List%60%2C%20or%20any%20other%20wrapper%20type%20that%20follows%20the%20same%20structure.%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20Functors%20in%20Haskell%20(optional)%0A%0A%20%20%20%20%20%20%20%20In%20Haskell%2C%20the%20type%20of%20%60fmap%60%20is%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20fmap%20%3A%3A%20Functor%20f%20%3D%3E%20(a%20-%3E%20b)%20-%3E%20f%20a%20-%3E%20f%20b%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20or%20equivalently%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20fmap%20%3A%3A%20Functor%20f%20%3D%3E%20(a%20-%3E%20b)%20-%3E%20(f%20a%20-%3E%20f%20b)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20This%20means%20that%20%60fmap%60%20**lifts**%20an%20ordinary%20function%20into%20the%20**functor%20world**%2C%20allowing%20it%20to%20operate%20within%20a%20computational%20context.%0A%0A%20%20%20%20%20%20%20%20Now%2C%20let's%20define%20an%20abstract%20class%20for%20%60Functor%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Defining%20Functor%0A%0A%20%20%20%20%20%20%20%20Recall%20that%2C%20a%20**Functor**%20is%20an%20abstraction%20that%20allows%20us%20to%20apply%20a%20function%20to%20values%20inside%20a%20computational%20context%20while%20preserving%20its%20structure.%20%0A%0A%20%20%20%20%20%20%20%20To%20define%20%60Functor%60%20in%20Python%2C%20we%20use%20an%20abstract%20base%20class%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%20Functor%5BA%5D(ABC)%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%20fmap(g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%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%20%20%20%20%20raise%20NotImplementedError%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20We%20can%20now%20extend%20custom%20wrappers%2C%20containers%2C%20or%20computation%20contexts%20with%20this%20%60Functor%60%20base%20class%2C%20implement%20the%20%60fmap%60%20method%2C%20and%20apply%20any%20function.%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%20More%20Functor%20instances%20(optional)%0A%0A%20%20%20%20%20%20%20%20In%20this%20section%2C%20we%20will%20explore%20more%20*Functor*%20instances%20to%20help%20you%20build%20up%20a%20better%20comprehension.%0A%0A%20%20%20%20%20%20%20%20The%20main%20reference%20is%20%5BData.Functor%5D(https%3A%2F%2Fhackage.haskell.org%2Fpackage%2Fbase-4.21.0.0%2Fdocs%2FData-Functor.html)%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%20%5BMaybe%5D(https%3A%2F%2Fhackage.haskell.org%2Fpackage%2Fbase-4.21.0.0%2Fdocs%2FData-Maybe.html%23t%3AMaybe)%20Functor%0A%0A%20%20%20%20%20%20%20%20**%60Maybe%60**%20is%20a%20functor%20that%20can%20either%20hold%20a%20value%20(%60Just(value)%60)%20or%20be%20%60Nothing%60%20(equivalent%20to%20%60None%60%20in%20Python).%20%0A%0A%20%20%20%20%20%20%20%20-%20It%20the%20value%20exists%2C%20%60fmap%60%20applies%20the%20function%20to%20this%20value%20inside%20the%20functor.%0A%20%20%20%20%20%20%20%20-%20If%20the%20value%20is%20%60None%60%2C%20%60fmap%60%20simply%20returns%20%60None%60.%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%0A%20%20%20%20%20%20%20%20By%20using%20%60Maybe%60%20as%20a%20functor%2C%20we%20gain%20the%20ability%20to%20apply%20transformations%20(%60fmap%60)%20to%20potentially%20absent%20values%2C%20without%20having%20to%20explicitly%20handle%20the%20%60None%60%20case%20every%20time.%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20We%20can%20implement%20the%20%60Maybe%60%20functor%20as%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_(B%2C%20Callable%2C%20Functor%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Maybe%5BA%5D(Functor)%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%20fmap(cls%2C%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%3A%20%22Maybe%5BA%5D%22)%20-%3E%20%22Maybe%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(None)%20if%20fa.value%20is%20None%20else%20cls(g(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%0Adef%20_(Maybe%2C%20pp)%3A%0A%20%20%20%20pp(Maybe.fmap(lambda%20x%3A%20x%20%2B%201%2C%20Maybe(1)))%0A%20%20%20%20pp(Maybe.fmap(lambda%20x%3A%20x%20%2B%201%2C%20Maybe(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%20The%20%5BEither%5D(https%3A%2F%2Fhackage.haskell.org%2Fpackage%2Fbase-4.21.0.0%2Fdocs%2FData-Either.html%23t%3AEither)%20Functor%0A%0A%20%20%20%20%20%20%20%20The%20%60Either%60%20type%20represents%20values%20with%20two%20possibilities%3A%20a%20value%20of%20type%20%60Either%20a%20b%60%20is%20either%20%60Left%20a%60%20or%20%60Right%20b%60.%0A%0A%20%20%20%20%20%20%20%20The%20%60Either%60%20type%20is%20sometimes%20used%20to%20represent%20a%20value%20which%20is%20**either%20correct%20or%20an%20error**%3B%20by%20convention%2C%20the%20%60left%60%20attribute%20is%20used%20to%20hold%20an%20error%20value%20and%20the%20%60right%60%20attribute%20is%20used%20to%20hold%20a%20correct%20value.%0A%0A%20%20%20%20%20%20%20%20%60fmap%60%20for%20%60Either%60%20will%20ignore%20Left%20values%2C%20but%20will%20apply%20the%20supplied%20function%20to%20values%20contained%20in%20the%20Right.%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_(B%2C%20Callable%2C%20Functor%2C%20Union%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Either%5BA%5D(Functor)%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%20raise%20TypeError(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%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%20)%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%0Adef%20_(Either)%3A%0A%20%20%20%20print(Either.fmap(lambda%20x%3A%20x%20%2B%201%2C%20Either(left%3DTypeError(%22Parse%20Error%22))))%0A%20%20%20%20print(Either.fmap(lambda%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20The%20%5BRoseTree%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FRose_tree)%20Functor%0A%0A%20%20%20%20%20%20%20%20A%20**RoseTree**%20is%20a%20tree%20where%3A%0A%0A%20%20%20%20%20%20%20%20-%20Each%20node%20holds%20a%20**value**.%0A%20%20%20%20%20%20%20%20-%20Each%20node%20has%20a%20**list%20of%20child%20nodes**%20(which%20are%20also%20RoseTrees).%0A%0A%20%20%20%20%20%20%20%20This%20structure%20is%20useful%20for%20representing%20hierarchical%20data%2C%20such%20as%3A%0A%0A%20%20%20%20%20%20%20%20-%20Abstract%20Syntax%20Trees%20(ASTs)%0A%20%20%20%20%20%20%20%20-%20File%20system%20directories%0A%20%20%20%20%20%20%20%20-%20Recursive%20computations%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_(B%2C%20Callable%2C%20Functor%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20RoseTree%5BA%5D(Functor)%3A%0A%20%20%20%20%20%20%20%20value%3A%20A%20%20%23%20The%20value%20stored%20in%20the%20node.%0A%20%20%20%20%20%20%20%20children%3A%20list%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22RoseTree%5BA%5D%22%0A%20%20%20%20%20%20%20%20%5D%20%20%23%20A%20list%20of%20child%20nodes%20forming%20the%20tree%20structure.%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20fmap(cls%2C%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%3A%20%22RoseTree%5BA%5D%22)%20-%3E%20%22RoseTree%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%20Applies%20a%20function%20to%20each%20value%20in%20the%20tree%2C%20producing%20a%20new%20%60RoseTree%5Bb%5D%60%20with%20transformed%20values.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%201.%20%60g%60%20is%20applied%20to%20the%20root%20node's%20%60value%60.%0A%20%20%20%20%20%20%20%20%20%20%20%202.%20Each%20child%20in%20%60children%60%20recursively%20calls%20%60fmap%60.%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%20RoseTree(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20g(fa.value)%2C%20%5Bcls.fmap(g%2C%20child)%20for%20child%20in%20fa.children%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20def%20__repr__(self)%20-%3E%20str%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20f%22Node%3A%20%7Bself.value%7D%2C%20Children%3A%20%7Bself.children%7D%22%0A%20%20%20%20return%20(RoseTree%2C)%0A%0A%0A%40app.cell%0Adef%20_(RoseTree%2C%20pp)%3A%0A%20%20%20%20rosetree%20%3D%20RoseTree(1%2C%20%5BRoseTree(2%2C%20%5B%5D)%2C%20RoseTree(3%2C%20%5BRoseTree(4%2C%20%5B%5D)%5D)%5D)%0A%0A%20%20%20%20pp(rosetree)%0A%20%20%20%20pp(RoseTree.fmap(lambda%20x%3A%20%5Bx%5D%2C%20rosetree))%0A%20%20%20%20pp(RoseTree.fmap(lambda%20x%3A%20RoseTree(x%2C%20%5B%5D)%2C%20rosetree))%0A%20%20%20%20return%20(rosetree%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Generic%20Functions%20that%20can%20be%20Used%20with%20Any%20Functor%0A%0A%20%20%20%20%20%20%20%20One%20of%20the%20powerful%20features%20of%20functors%20is%20that%20we%20can%20write%20**generic%20functions**%20that%20can%20work%20with%20any%20functor.%0A%0A%20%20%20%20%20%20%20%20Remember%20that%20in%20Haskell%2C%20the%20type%20of%20%60fmap%60%20can%20be%20written%20as%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20fmap%20%3A%3A%20Functor%20f%20%3D%3E%20(a%20-%3E%20b)%20-%3E%20(f%20a%20-%3E%20f%20b)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20Translating%20to%20Python%2C%20we%20get%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20def%20fmap(g%3A%20Callable%5B%5BA%5D%2C%20B%5D)%20-%3E%20Callable%5B%5BFunctor%5BA%5D%5D%2C%20Functor%5BB%5D%5D%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20This%20means%20that%20%60fmap%60%3A%0A%0A%20%20%20%20%20%20%20%20-%20Takes%20an%20**ordinary%20function**%20%60Callable%5B%5BA%5D%2C%20B%5D%60%20as%20input.%0A%20%20%20%20%20%20%20%20-%20Outputs%20a%20function%20that%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Takes%20a%20**functor**%20of%20type%20%60Functor%5BA%5D%60%20as%20input.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Outputs%20a%20**functor**%20of%20type%20%60Functor%5BB%5D%60.%0A%0A%20%20%20%20%20%20%20%20Inspired%20by%20this%2C%20we%20can%20implement%20an%20%60inc%60%20function%20which%20takes%20a%20functor%2C%20applies%20the%20function%20%60lambda%20x%3A%20x%20%2B%201%60%20to%20every%20value%20inside%20it%2C%20and%20returns%20a%20new%20functor%20with%20the%20updated%20values.%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%20inc%20%3D%20lambda%20functor%3A%20functor.fmap(lambda%20x%3A%20x%20%2B%201%2C%20functor)%0A%20%20%20%20return%20(inc%2C)%0A%0A%0A%40app.cell%0Adef%20_(flist%2C%20inc%2C%20pp%2C%20rosetree%2C%20wrapper)%3A%0A%20%20%20%20pp(inc(wrapper))%0A%20%20%20%20pp(inc(flist))%0A%20%20%20%20pp(inc(rosetree))%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%20Implement%20other%20generic%20functions%20and%20apply%20them%20to%20different%20*Functor*%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(r%22%22%22%23%20Functor%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Functor%20laws%0A%0A%20%20%20%20%20%20%20%20In%20addition%20to%20providing%20a%20function%20%60fmap%60%20of%20the%20specified%20type%2C%20functors%20are%20also%20required%20to%20satisfy%20two%20equational%20laws%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60haskell%0A%20%20%20%20%20%20%20%20fmap%20id%20%3D%20id%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20--%20fmap%20preserves%20identity%0A%20%20%20%20%20%20%20%20fmap%20(g%20.%20h)%20%3D%20fmap%20g%20.%20fmap%20h%20%20--%20fmap%20distributes%20over%20composition%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%201.%20%60fmap%60%20should%20preserve%20the%20**identity%20function**%2C%20in%20the%20sense%20that%20applying%20%60fmap%60%20to%20this%20function%20returns%20the%20same%20function%20as%20the%20result.%0A%20%20%20%20%20%20%20%202.%20%60fmap%60%20should%20also%20preserve%20**function%20composition**.%20Applying%20two%20composed%20functions%20%60g%60%20and%20%60h%60%20to%20a%20functor%20via%20%60fmap%60%20should%20give%20the%20same%20result%20as%20first%20applying%20%60fmap%60%20to%20%60g%60%20and%20then%20applying%20%60fmap%60%20to%20%60h%60.%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%0A%20%20%20%20%20%20%20%20-%20Any%20%60Functor%60%20instance%20satisfying%20the%20first%20law%20%60(fmap%20id%20%3D%20id)%60%20will%20%5Bautomatically%20satisfy%20the%20second%20law%5D(https%3A%2F%2Fgithub.com%2Fquchen%2Farticles%2Fblob%2Fmaster%2Fsecond_functor_law.md)%20as%20well.%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%23%20Functor%20laws%20verification%0A%0A%20%20%20%20%20%20%20%20We%20can%20define%20%60id%60%20and%20%60compose%60%20in%20%60Python%60%20as%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_()%3A%0A%20%20%20%20id%20%3D%20lambda%20x%3A%20x%0A%20%20%20%20compose%20%3D%20lambda%20f%2C%20g%3A%20lambda%20x%3A%20f(g(x))%0A%20%20%20%20return%20(id%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22We%20can%20add%20a%20helper%20function%20%60check_functor_law%60%20to%20verify%20that%20an%20instance%20satisfies%20the%20functor%20laws%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(id)%3A%0A%20%20%20%20check_functor_law%20%3D%20lambda%20functor%3A%20repr(functor.fmap(id%2C%20functor))%20%3D%3D%20repr(%0A%20%20%20%20%20%20%20%20functor%0A%20%20%20%20)%0A%20%20%20%20return%20(check_functor_law%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22We%20can%20verify%20the%20functor%20we've%20defined%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(check_functor_law%2C%20flist%2C%20pp%2C%20rosetree%2C%20wrapper)%3A%0A%20%20%20%20for%20functor%20in%20(wrapper%2C%20flist%2C%20rosetree)%3A%0A%20%20%20%20%20%20%20%20pp(check_functor_law(functor))%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%22%22%22And%20here%20is%20an%20%60EvilFunctor%60.%20We%20can%20verify%20it's%20not%20a%20valid%20%60Functor%60.%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(B%2C%20Callable%2C%20Functor%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20EvilFunctor%5BA%5D(Functor)%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%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%22EvilFunctor%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22EvilFunctor%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls(%5Bfa.value%5B0%5D%5D%20*%202%20%2B%20%5Bg(x)%20for%20x%20in%20fa.value%5B1%3A%5D%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20fa.value%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20return%20(EvilFunctor%2C)%0A%0A%0A%40app.cell%0Adef%20_(EvilFunctor%2C%20check_functor_law%2C%20pp)%3A%0A%20%20%20%20pp(check_functor_law(EvilFunctor(%5B1%2C%202%2C%203%2C%204%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%20Utility%20functions%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%20const(cls%2C%20fa%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%20fa)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20void(cls%2C%20fa%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(fa%2C%20None)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20unzip(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fab%3A%20%22Functor%5Btuple%5BA%2C%20B%5D%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20tuple%5B%22Functor%5BA%5D%22%2C%20%22Functor%5BB%5D%22%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.fmap(lambda%20p%3A%20p%5B0%5D%2C%20fab)%2C%20cls.fmap(lambda%20p%3A%20p%5B1%5D%2C%20fab)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20%60const%60%20replaces%20all%20values%20inside%20a%20functor%20with%20a%20constant%20%60b%60%0A%20%20%20%20%20%20%20%20-%20%60void%60%20is%20equivalent%20to%20%60const(fa%2C%20None)%60%2C%20transforming%20all%20values%20in%20a%20functor%20into%20%60None%60%0A%20%20%20%20%20%20%20%20-%20%60unzip%60%20is%20a%20generalization%20of%20the%20regular%20*unzip*%20on%20a%20list%20of%20pairs%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_(List%2C%20Maybe)%3A%0A%20%20%20%20print(Maybe.const(Maybe(0)%2C%201))%0A%20%20%20%20print(Maybe.const(Maybe(None)%2C%201))%0A%20%20%20%20print(List.const(List(%5B1%2C%202%2C%203%2C%204%5D)%2C%201))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(List%2C%20Maybe)%3A%0A%20%20%20%20print(Maybe.void(Maybe(1)))%0A%20%20%20%20print(List.void(List(%5B1%2C%202%2C%203%5D)))%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(List%2C%20Maybe)%3A%0A%20%20%20%20print(Maybe.unzip(Maybe((%22Hello%22%2C%20%22World%22))))%0A%20%20%20%20print(List.unzip(List(%5B(%22I%22%2C%20%22love%22)%2C%20(%22really%22%2C%20%22%CE%BB%22)%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%20admonition%0A%20%20%20%20%20%20%20%20You%20can%20always%20override%20these%20utility%20functions%20with%20a%20more%20efficient%20implementation%20for%20specific%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%0Adef%20_(List%2C%20RoseTree%2C%20flist%2C%20pp%2C%20rosetree)%3A%0A%20%20%20%20pp(RoseTree.const(rosetree%2C%20%22%CE%BB%22))%0A%20%20%20%20pp(RoseTree.void(rosetree))%0A%20%20%20%20pp(List.const(flist%2C%20%22%CE%BB%22))%0A%20%20%20%20pp(List.void(flist))%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%22%22%22%23%20Formal%20implementation%20of%20Functor%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%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%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%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%20raise%20NotImplementedError(%22Subclasses%20must%20implement%20fmap%22)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20const(cls%2C%20fa%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%20fa)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20void(cls%2C%20fa%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(fa%2C%20None)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20unzip(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20fab%3A%20%22Functor%5Btuple%5BA%2C%20B%5D%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20tuple%5B%22Functor%5BA%5D%22%2C%20%22Functor%5BB%5D%22%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.fmap(lambda%20p%3A%20p%5B0%5D%2C%20fab)%2C%20cls.fmap(lambda%20p%3A%20p%5B1%5D%2C%20fab)%0A%20%20%20%20return%20(Functor%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Limitations%20of%20Functor%0A%0A%20%20%20%20%20%20%20%20Functors%20abstract%20the%20idea%20of%20mapping%20a%20function%20over%20each%20element%20of%20a%20structure.%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%0A%20%20%20%20%20%20%20%20We%20will%20learn%20how%20to%20resolve%20this%20problem%20in%20the%20next%20notebook%20on%20%60Applicatives%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Introduction%20to%20Categories%0A%0A%20%20%20%20%20%20%20%20A%20%5Bcategory%5D(https%3A%2F%2Fen.wikibooks.org%2Fwiki%2FHaskell%2FCategory_theory%23Introduction_to_categories)%20is%2C%20in%20essence%2C%20a%20simple%20collection.%20It%20has%20three%20components%3A%20%0A%0A%20%20%20%20%20%20%20%20-%20A%20collection%20of%20**objects**.%0A%20%20%20%20%20%20%20%20-%20A%20collection%20of%20**morphisms**%2C%20each%20of%20which%20ties%20two%20objects%20(a%20_source%20object_%20and%20a%20_target%20object_)%20together.%20If%20%24f%24%20is%20a%20morphism%20with%20source%20object%20%24C%24%20and%20target%20object%20%24B%24%2C%20we%20write%20%24f%20%3A%20C%20%E2%86%92%20B%24.%0A%20%20%20%20%20%20%20%20-%20A%20notion%20of%20**composition**%20of%20these%20morphisms.%20If%20%24g%20%3A%20A%20%E2%86%92%20B%24%20and%20%24f%20%3A%20B%20%E2%86%92%20C%24%20are%20two%20morphisms%2C%20they%20can%20be%20composed%2C%20resulting%20in%20a%20morphism%20%24f%20%E2%88%98%20g%20%3A%20A%20%E2%86%92%20C%24.%0A%0A%20%20%20%20%20%20%20%20%23%23%20Category%20laws%0A%0A%20%20%20%20%20%20%20%20There%20are%20three%20laws%20that%20categories%20need%20to%20follow.%20%0A%0A%20%20%20%20%20%20%20%201.%20The%20composition%20of%20morphisms%20needs%20to%20be%20**associative**.%20Symbolically%2C%20%24f%20%E2%88%98%20(g%20%E2%88%98%20h)%20%3D%20(f%20%E2%88%98%20g)%20%E2%88%98%20h%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Morphisms%20are%20applied%20right%20to%20left%2C%20so%20with%20%24f%20%E2%88%98%20g%24%20first%20%24g%24%20is%20applied%2C%20then%20%24f%24.%20%0A%0A%20%20%20%20%20%20%20%202.%20The%20category%20needs%20to%20be%20**closed**%20under%20the%20composition%20operation.%20So%20if%20%24f%20%3A%20B%20%E2%86%92%20C%24%20and%20%24g%20%3A%20A%20%E2%86%92%20B%24%2C%20then%20there%20must%20be%20some%20morphism%20%24h%20%3A%20A%20%E2%86%92%20C%24%20in%20the%20category%20such%20that%20%24h%20%3D%20f%20%E2%88%98%20g%24.%20%0A%0A%20%20%20%20%20%20%20%203.%20Given%20a%20category%20%24C%24%20there%20needs%20to%20be%20for%20every%20object%20%24A%24%20an%20**identity**%20morphism%2C%20%24id_A%20%3A%20A%20%E2%86%92%20A%24%20that%20is%20an%20identity%20of%20composition%20with%20other%20morphisms.%20Put%20precisely%2C%20for%20every%20morphism%20%24g%20%3A%20A%20%E2%86%92%20B%24%3A%20%24g%20%E2%88%98%20id_A%20%3D%20id_B%20%E2%88%98%20g%20%3D%20g%24%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20attention%20%7C%20The%20definition%20of%20a%20category%20does%20not%20define%3A%20%0A%0A%20%20%20%20%20%20%20%20-%20what%20%60%E2%88%98%60%20is%2C%0A%20%20%20%20%20%20%20%20-%20what%20%60id%60%20is%2C%20or%0A%20%20%20%20%20%20%20%20-%20what%20%60f%60%2C%20%60g%60%2C%20and%20%60h%60%20might%20be.%20%0A%0A%20%20%20%20%20%20%20%20Instead%2C%20category%20theory%20leaves%20it%20up%20to%20us%20to%20discover%20what%20they%20might%20be.%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20The%20Python%20category%0A%0A%20%20%20%20%20%20%20%20The%20main%20category%20we'll%20be%20concerning%20ourselves%20with%20in%20this%20part%20is%20the%20Python%20category%2C%20or%20we%20can%20give%20it%20a%20shorter%20name%3A%20%60Py%60.%20%60Py%60%20treats%20Python%20types%20as%20objects%20and%20Python%20functions%20as%20morphisms.%20A%20function%20%60def%20f(a%3A%20A)%20-%3E%20B%60%20for%20types%20A%20and%20B%20is%20a%20morphism%20in%20Python.%0A%0A%20%20%20%20%20%20%20%20Remember%20that%20we%20defined%20the%20%60id%60%20and%20%60compose%60%20function%20above%20as%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60Python%0A%20%20%20%20%20%20%20%20def%20id(x%3A%20A)%20-%3E%20A%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20x%0A%0A%20%20%20%20%20%20%20%20def%20compose(f%3A%20Callable%5B%5BB%5D%2C%20C%5D%2C%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D)%20-%3E%20Callable%5B%5BA%5D%2C%20C%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20lambda%20x%3A%20f(g(x))%20%20%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20We%20can%20check%20second%20law%20easily.%20%0A%0A%20%20%20%20%20%20%20%20For%20the%20first%20law%2C%20we%20have%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%23%20compose(f%2C%20g)%20%3D%20lambda%20x%3A%20f(g(x))%0A%20%20%20%20%20%20%20%20f%20%E2%88%98%20(g%20%E2%88%98%20h)%20%0A%20%20%20%20%20%20%20%20%3D%20compose(f%2C%20compose(g%2C%20h))%20%0A%20%20%20%20%20%20%20%20%3D%20lambda%20x%3A%20f(compose(g%2C%20h)(x))%0A%20%20%20%20%20%20%20%20%3D%20lambda%20x%3A%20f(lambda%20y%3A%20g(h(y))(x))%0A%20%20%20%20%20%20%20%20%3D%20lambda%20x%3A%20f(g(h(x)))%0A%0A%20%20%20%20%20%20%20%20(f%20%E2%88%98%20g)%20%E2%88%98%20h%20%0A%20%20%20%20%20%20%20%20%3D%20compose(compose(f%2C%20g)%2C%20h)%0A%20%20%20%20%20%20%20%20%3D%20lambda%20x%3A%20compose(f%2C%20g)(h(x))%0A%20%20%20%20%20%20%20%20%3D%20lambda%20x%3A%20lambda%20y%3A%20f(g(y))(h(x))%0A%20%20%20%20%20%20%20%20%3D%20lambda%20x%3A%20f(g(h(x)))%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20For%20the%20third%20law%2C%20we%20have%3A%20%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20g%20%E2%88%98%20id_A%20%0A%20%20%20%20%20%20%20%20%3D%20compose(g%3A%20Callable%5B%5Ba%5D%2C%20b%5D%2C%20id%3A%20Callable%5B%5Ba%5D%2C%20a%5D)%20-%3E%20Callable%5B%5Ba%5D%2C%20b%5D%0A%20%20%20%20%20%20%20%20%3D%20lambda%20x%3A%20g(id(x))%0A%20%20%20%20%20%20%20%20%3D%20lambda%20x%3A%20g(x)%20%23%20id(x)%20%3D%20x%0A%20%20%20%20%20%20%20%20%3D%20g%0A%20%20%20%20%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20the%20similar%20proof%20can%20be%20applied%20to%20%24id_B%20%E2%88%98%20g%20%3Dg%24.%0A%0A%20%20%20%20%20%20%20%20Thus%20%60Py%60%20is%20a%20valid%20category.%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Functors%2C%20again%0A%0A%20%20%20%20%20%20%20%20A%20functor%20is%20essentially%20a%20transformation%20between%20categories%2C%20so%20given%20categories%20%24C%24%20and%20%24D%24%2C%20a%20functor%20%24F%20%3A%20C%20%E2%86%92%20D%24%3A%0A%0A%20%20%20%20%20%20%20%20-%20Maps%20any%20object%20%24A%24%20in%20%24C%24%20to%20%24F%20(%20A%20)%24%2C%20in%20%24D%24.%0A%20%20%20%20%20%20%20%20-%20Maps%20morphisms%20%24f%20%3A%20A%20%E2%86%92%20B%24%20in%20%24C%24%20to%20%24F%20(%20f%20)%20%3A%20F%20(%20A%20)%20%E2%86%92%20F%20(%20B%20)%24%20in%20%24D%24.%0A%0A%20%20%20%20%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%0A%0A%20%20%20%20%20%20%20%20Endofunctors%20are%20functors%20from%20a%20category%20to%20itself.%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Functors%20on%20the%20category%20of%20Python%0A%0A%20%20%20%20%20%20%20%20Remember%20that%20a%20functor%20has%20two%20parts%3A%20it%20maps%20objects%20in%20one%20category%20to%20objects%20in%20another%20and%20morphisms%20in%20the%20first%20category%20to%20morphisms%20in%20the%20second.%20%0A%0A%20%20%20%20%20%20%20%20Functors%20in%20Python%20are%20from%20%60Py%60%20to%20%60Func%60%2C%20where%20%60Func%60%20is%20the%20subcategory%20of%20%60Py%60%20defined%20on%20just%20that%20functor's%20types.%20E.g.%20the%20RoseTree%20functor%20goes%20from%20%60Py%60%20to%20%60RoseTree%60%2C%20where%20%60RoseTree%60%20is%20the%20category%20containing%20only%20RoseTree%20types%2C%20that%20is%2C%20%60RoseTree%5BT%5D%60%20for%20any%20type%20%60T%60.%20The%20morphisms%20in%20%60RoseTree%60%20are%20functions%20defined%20on%20RoseTree%20types%2C%20that%20is%2C%20functions%20%60Callable%5B%5BRoseTree%5BT%5D%5D%2C%20RoseTree%5BU%5D%5D%60%20for%20types%20%60T%60%2C%20%60U%60.%0A%0A%20%20%20%20%20%20%20%20Recall%20the%20definition%20of%20%60Functor%60%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%20Functor%5BA%5D(ABC)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20And%20RoseTree%3A%20%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%20RoseTree%5BA%5D(Functor)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20**Here's%20the%20key%20part%3A**%20the%20_type%20constructor_%20%60RoseTree%60%20takes%20any%20type%20%60T%60%20to%20a%20new%20type%2C%20%60RoseTree%5BT%5D%60.%20Also%2C%20%60fmap%60%20restricted%20to%20%60RoseTree%60%20types%20takes%20a%20function%20%60Callable%5B%5BA%5D%2C%20B%5D%60%20to%20a%20function%20%60Callable%5B%5BRoseTree%5BA%5D%5D%2C%20RoseTree%5BB%5D%5D%60.%0A%0A%20%20%20%20%20%20%20%20But%20that's%20it.%20We've%20defined%20two%20parts%2C%20something%20that%20takes%20objects%20in%20%60Py%60%20to%20objects%20in%20another%20category%20(that%20of%20%60RoseTree%60%20types%20and%20functions%20defined%20on%20%60RoseTree%60%20types)%2C%20and%20something%20that%20takes%20morphisms%20in%20%60Py%60%20to%20morphisms%20in%20this%20category.%20So%20%60RoseTree%60%20is%20a%20functor.%20%0A%0A%20%20%20%20%20%20%20%20To%20sum%20up%3A%0A%0A%20%20%20%20%20%20%20%20-%20We%20work%20in%20the%20category%20**Py**%20and%20its%20subcategories.%20%20%0A%20%20%20%20%20%20%20%20-%20**Objects**%20are%20types%20(e.g.%2C%20%60int%60%2C%20%60str%60%2C%20%60list%60).%20%20%0A%20%20%20%20%20%20%20%20-%20**Morphisms**%20are%20functions%20(%60Callable%5B%5BA%5D%2C%20B%5D%60).%20%20%0A%20%20%20%20%20%20%20%20-%20**Things%20that%20take%20a%20type%20and%20return%20another%20type**%20are%20type%20constructors%20(%60RoseTree%5BT%5D%60).%20%20%0A%20%20%20%20%20%20%20%20-%20**Things%20that%20take%20a%20function%20and%20return%20another%20function**%20are%20higher-order%20functions%20(%60Callable%5B%5BCallable%5B%5BA%5D%2C%20B%5D%5D%2C%20Callable%5B%5BC%5D%2C%20D%5D%5D%60).%20%20%0A%20%20%20%20%20%20%20%20-%20**Abstract%20base%20classes%20(ABC)**%20and%20duck%20typing%20provide%20a%20way%20to%20express%20polymorphism%2C%20capturing%20the%20idea%20that%20in%20category%20theory%2C%20structures%20are%20often%20defined%20over%20multiple%20objects%20at%20once.%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Functor%20laws%2C%20again%0A%0A%20%20%20%20%20%20%20%20Once%20again%20there%20are%20a%20few%20axioms%20that%20functors%20have%20to%20obey.%20%0A%0A%20%20%20%20%20%20%20%201.%20Given%20an%20identity%20morphism%20%24id_A%24%20on%20an%20object%20%24A%24%2C%20%24F%20(%20id_A%20)%24%20must%20be%20the%20identity%20morphism%20on%20%24F%20(%20A%20)%24.%3A%0A%0A%20%20%20%20%20%20%20%20%24%24F(%7Bid%7D%20_%7BA%7D)%3D%7Bid%7D%20_%7BF(A)%7D%24%24%0A%0A%20%20%20%20%20%20%20%203.%20Functors%20must%20distribute%20over%20morphism%20composition.%0A%0A%20%20%20%20%20%20%20%20%24%24F(f%5Ccirc%20g)%3DF(f)%5Ccirc%20F(g)%24%24%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%20%22%22%22%0A%20%20%20%20%20%20%20%20Remember%20that%20we%20defined%20the%20%60id%60%20and%20%60compose%60%20as%20%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20id%20%3D%20lambda%20x%3A%20x%0A%20%20%20%20%20%20%20%20compose%20%3D%20lambda%20f%2C%20g%3A%20lambda%20x%3A%20f(g(x))%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20We%20can%20define%20%60fmap%60%20as%3A%20%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20fmap%20%3D%20lambda%20g%2C%20functor%3A%20functor.fmap(g%2C%20functor)%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%20prove%20that%20%60fmap%60%20is%20a%20functor.%0A%0A%20%20%20%20%20%20%20%20First%2C%20let's%20define%20a%20%60Category%60%20for%20a%20specific%20%60Functor%60.%20We%20choose%20to%20define%20the%20%60Category%60%20for%20the%20%60Wrapper%60%20as%20%60WrapperCategory%60%20here%20for%20simplicity%2C%20but%20remember%20that%20%60Wrapper%60%20can%20be%20any%20%60Functor%60(i.e.%20%60List%60%2C%20%60RoseTree%60%2C%20%60Maybe%60%20and%20more)%3A%0A%0A%20%20%20%20%20%20%20%20We%20define%20%60WrapperCategory%60%20as%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%20WrapperCategory%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20id(wrapper%3A%20Wrapper%5BA%5D)%20-%3E%20Wrapper%5BA%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20Wrapper(wrapper.value)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20%20%20%20%20def%20compose(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%3A%20Callable%5B%5BWrapper%5BB%5D%5D%2C%20Wrapper%5BC%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20g%3A%20Callable%5B%5BWrapper%5BA%5D%5D%2C%20Wrapper%5BB%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20wrapper%3A%20Wrapper%5BA%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%20-%3E%20Callable%5B%5BWrapper%5BA%5D%5D%2C%20Wrapper%5BC%5D%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20f(g(Wrapper(wrapper.value)))%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20And%20%60Wrapper%60%20is%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%20Wrapper%5BA%5D(Functor)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20value%3A%20A%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%20fmap(cls%2C%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20fa%3A%20%22Wrapper%5BA%5D%22)%20-%3E%20%22Wrapper%5BB%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20Wrapper(g(fa.value))%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%20%22%22%22%0A%20%20%20%20%20%20%20%20We%20can%20prove%20that%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20fmap(id%2C%20wrapper)%0A%20%20%20%20%20%20%20%20%3D%20Wrapper.fmap(id%2C%20wrapper)%0A%20%20%20%20%20%20%20%20%3D%20Wrapper(id(wrapper.value))%0A%20%20%20%20%20%20%20%20%3D%20Wrapper(wrapper.value)%0A%20%20%20%20%20%20%20%20%3D%20WrapperCategory.id(wrapper)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20and%3A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20fmap(compose(f%2C%20g)%2C%20wrapper)%0A%20%20%20%20%20%20%20%20%3D%20Wrapper.fmap(compose(f%2C%20g)%2C%20wrapper)%0A%20%20%20%20%20%20%20%20%3D%20Wrapper(compose(f%2C%20g)(wrapper.value))%0A%20%20%20%20%20%20%20%20%3D%20Wrapper(f(g(wrapper.value)))%0A%0A%20%20%20%20%20%20%20%20WrapperCategory.compose(fmap(f%2C%20wrapper)%2C%20fmap(g%2C%20wrapper)%2C%20wrapper)%0A%20%20%20%20%20%20%20%20%3D%20fmap(f%2C%20wrapper)(fmap(g%2C%20wrapper)(wrapper))%0A%20%20%20%20%20%20%20%20%3D%20fmap(f%2C%20wrapper)(Wrapper.fmap(g%2C%20wrapper))%0A%20%20%20%20%20%20%20%20%3D%20fmap(f%2C%20wrapper)(Wrapper(g(wrapper.value)))%0A%20%20%20%20%20%20%20%20%3D%20Wrapper.fmap(f%2C%20Wrapper(g(wrapper.value)))%0A%20%20%20%20%20%20%20%20%3D%20Wrapper(f(Wrapper(g(wrapper.value)).value))%0A%20%20%20%20%20%20%20%20%3D%20Wrapper(f(g(wrapper.value)))%20%20%23%20Wrapper(g(wrapper.value)).value%20%3D%20g(wrapper.value)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20So%20our%20%60Wrapper%60%20is%20a%20valid%20%60Functor%60.%0A%0A%20%20%20%20%20%20%20%20%3E%20Try%20validating%20functor%20laws%20for%20%60Wrapper%60%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_(A%2C%20B%2C%20C%2C%20Callable%2C%20Wrapper%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20WrapperCategory%3A%0A%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20def%20id(wrapper%3A%20Wrapper%5BA%5D)%20-%3E%20Wrapper%5BA%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20Wrapper(wrapper.value)%0A%0A%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20def%20compose(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%3A%20Callable%5B%5BWrapper%5BB%5D%5D%2C%20Wrapper%5BC%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20g%3A%20Callable%5B%5BWrapper%5BA%5D%5D%2C%20Wrapper%5BB%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20wrapper%3A%20Wrapper%5BA%5D%2C%0A%20%20%20%20%20%20%20%20)%20-%3E%20Callable%5B%5BWrapper%5BA%5D%5D%2C%20Wrapper%5BC%5D%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20f(g(Wrapper(wrapper.value)))%0A%20%20%20%20return%20(WrapperCategory%2C)%0A%0A%0A%40app.cell%0Adef%20_(WrapperCategory%2C%20id%2C%20pp%2C%20wrapper)%3A%0A%20%20%20%20pp(wrapper.fmap(id%2C%20wrapper)%20%3D%3D%20WrapperCategory.id(wrapper))%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Length%20as%20a%20Functor%0A%0A%20%20%20%20%20%20%20%20Remember%20that%20a%20functor%20is%20a%20transformation%20between%20two%20categories.%20It%20is%20not%20only%20limited%20to%20a%20functor%20from%20%60Py%60%20to%20%60Func%60%2C%20but%20also%20includes%20transformations%20between%20other%20mathematical%20structures.%0A%0A%20%20%20%20%20%20%20%20Let%E2%80%99s%20prove%20that%20**%60length%60**%20can%20be%20viewed%20as%20a%20functor.%20Specifically%2C%20we%20will%20demonstrate%20that%20%60length%60%20is%20a%20functor%20from%20the%20**category%20of%20list%20concatenation**%20to%20the%20**category%20of%20integer%20addition**.%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20Category%20of%20List%20Concatenation%0A%0A%20%20%20%20%20%20%20%20First%2C%20let%E2%80%99s%20define%20the%20category%20of%20list%20concatenation%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%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20ListConcatenation%5BA%5D%3A%0A%20%20%20%20%20%20%20%20value%3A%20list%5BA%5D%0A%0A%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20def%20id()%20-%3E%20%22ListConcatenation%5BA%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20ListConcatenation(%5B%5D)%0A%0A%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20def%20compose(%0A%20%20%20%20%20%20%20%20%20%20%20%20this%3A%20%22ListConcatenation%5BA%5D%22%2C%20other%3A%20%22ListConcatenation%5BA%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22ListConcatenation%5Ba%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20ListConcatenation(this.value%20%2B%20other.value)%0A%20%20%20%20return%20(ListConcatenation%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%20%22%22%22%0A%20%20%20%20%20%20%20%20-%20**Identity**%3A%20The%20identity%20element%20is%20an%20empty%20list%20(%60ListConcatenation(%5B%5D)%60).%0A%20%20%20%20%20%20%20%20-%20**Composition**%3A%20The%20composition%20of%20two%20lists%20is%20their%20concatenation%20(%60this.value%20%2B%20other.value%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Category%20of%20Integer%20Addition%0A%0A%20%20%20%20%20%20%20%20Now%2C%20let's%20define%20the%20category%20of%20integer%20addition%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_(dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20IntAddition%3A%0A%20%20%20%20%20%20%20%20value%3A%20int%0A%0A%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20def%20id()%20-%3E%20%22IntAddition%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20IntAddition(0)%0A%0A%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20def%20compose(this%3A%20%22IntAddition%22%2C%20other%3A%20%22IntAddition%22)%20-%3E%20%22IntAddition%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20IntAddition(this.value%20%2B%20other.value)%0A%20%20%20%20return%20(IntAddition%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%20%22%22%22%0A%20%20%20%20%20%20%20%20-%20**Identity**%3A%20The%20identity%20element%20is%20%60IntAddition(0)%60%20(the%20additive%20identity).%0A%20%20%20%20%20%20%20%20-%20**Composition**%3A%20The%20composition%20of%20two%20integers%20is%20their%20sum%20(%60this.value%20%2B%20other.value%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Defining%20the%20Length%20Functor%0A%0A%20%20%20%20%20%20%20%20We%20now%20define%20the%20%60length%60%20function%20as%20a%20functor%2C%20mapping%20from%20the%20category%20of%20list%20concatenation%20to%20the%20category%20of%20integer%20addition%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20length%20%3D%20lambda%20l%3A%20IntAddition(len(l.value))%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_(IntAddition)%3A%0A%20%20%20%20length%20%3D%20lambda%20l%3A%20IntAddition(len(l.value))%0A%20%20%20%20return%20(length%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%22%22%22This%20function%20takes%20an%20instance%20of%20%60ListConcatenation%60%2C%20computes%20its%20length%2C%20and%20returns%20an%20%60IntAddition%60%20instance%20with%20the%20computed%20length.%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Verifying%20Functor%20Laws%0A%0A%20%20%20%20%20%20%20%20Now%2C%20let%E2%80%99s%20verify%20that%20%60length%60%20satisfies%20the%20two%20functor%20laws.%0A%0A%20%20%20%20%20%20%20%20**Identity%20Law**%0A%0A%20%20%20%20%20%20%20%20The%20identity%20law%20states%20that%20applying%20the%20functor%20to%20the%20identity%20element%20of%20one%20category%20should%20give%20the%20identity%20element%20of%20the%20other%20category.%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_(IntAddition%2C%20ListConcatenation%2C%20length%2C%20pp)%3A%0A%20%20%20%20pp(length(ListConcatenation.id())%20%3D%3D%20IntAddition.id())%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%22%22%22This%20ensures%20that%20the%20length%20of%20an%20empty%20list%20(identity%20in%20the%20%60ListConcatenation%60%20category)%20is%20%600%60%20(identity%20in%20the%20%60IntAddition%60%20category).%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%20%22%22%22%0A%20%20%20%20%20%20%20%20**Composition%20Law**%0A%0A%20%20%20%20%20%20%20%20The%20composition%20law%20states%20that%20the%20functor%20should%20preserve%20composition.%20Applying%20the%20functor%20to%20a%20composed%20element%20should%20be%20the%20same%20as%20composing%20the%20functor%20applied%20to%20the%20individual%20elements.%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_(IntAddition%2C%20ListConcatenation%2C%20length%2C%20pp)%3A%0A%20%20%20%20lista%20%3D%20ListConcatenation(%5B1%2C%202%5D)%0A%20%20%20%20listb%20%3D%20ListConcatenation(%5B3%2C%204%5D)%0A%20%20%20%20pp(%0A%20%20%20%20%20%20%20%20length(ListConcatenation.compose(lista%2C%20listb))%0A%20%20%20%20%20%20%20%20%3D%3D%20IntAddition.compose(length(lista)%2C%20length(listb))%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(%22%22%22This%20ensures%20that%20the%20length%20of%20the%20concatenation%20of%20two%20lists%20is%20the%20same%20as%20the%20sum%20of%20the%20lengths%20of%20the%20individual%20lists.%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%20Bifunctor%0A%0A%20%20%20%20%20%20%20%20A%20%60Bifunctor%60%20is%20a%20type%20constructor%20that%20takes%20two%20type%20arguments%20and%20**is%20a%20functor%20in%20both%20arguments.**%20%0A%0A%20%20%20%20%20%20%20%20For%20example%2C%20think%20about%20%60Either%60's%20usual%20%60Functor%60%20instance.%20It%20only%20allows%20you%20to%20fmap%20over%20the%20second%20type%20parameter%3A%20%60right%60%20values%20get%20mapped%2C%20%60left%60%20values%20stay%20as%20they%20are.%0A%0A%20%20%20%20%20%20%20%20However%2C%20its%20%60Bifunctor%60%20instance%20allows%20you%20to%20map%20both%20halves%20of%20the%20sum.%0A%0A%20%20%20%20%20%20%20%20There%20are%20three%20core%20methods%20for%20%60Bifunctor%60%3A%20%0A%0A%20%20%20%20%20%20%20%20-%20%60bimap%60%20allows%20mapping%20over%20both%20type%20arguments%20at%20once.%0A%20%20%20%20%20%20%20%20-%20%60first%60%20and%20%60second%60%20are%20also%20provided%20for%20mapping%20over%20only%20one%20type%20argument%20at%20a%20time.%0A%0A%0A%20%20%20%20%20%20%20%20The%20abstraction%20of%20%60Bifunctor%60%20is%3A%20%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%20B%2C%20Callable%2C%20D%2C%20dataclass%2C%20f%2C%20id)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Bifunctor%5BA%2C%20C%5D(ABC)%3A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20bimap(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20h%3A%20Callable%5B%5BC%5D%2C%20D%5D%2C%20fa%3A%20%22Bifunctor%5BA%2C%20C%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Bifunctor%5BB%2C%20D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.first(f%2C%20cls.second(g%2C%20fa))%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20first(%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%22Bifunctor%5BA%2C%20C%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Bifunctor%5BB%2C%20C%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.bimap(g%2C%20id%2C%20fa)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20second(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20g%3A%20Callable%5B%5BB%5D%2C%20C%5D%2C%20fa%3A%20%22Bifunctor%5BA%2C%20B%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22Bifunctor%5BA%2C%20C%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls.bimap(id%2C%20g%2C%20fa)%0A%20%20%20%20return%20(Bifunctor%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%20%7C%20minimal%20implementation%20requirement%0A%20%20%20%20%20%20%20%20-%20%60bimap%60%20or%20both%20%60first%60%20and%20%60second%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%23%20Instances%20of%20Bifunctor%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%23%20The%20Either%20Bifunctor%0A%0A%20%20%20%20%20%20%20%20For%20the%20%60Either%20Bifunctor%60%2C%20we%20allow%20it%20to%20map%20a%20function%20over%20the%20%60left%60%20value%20as%20well.%0A%0A%20%20%20%20%20%20%20%20Notice%20that%2C%20the%20%60Either%20Bifunctor%60%20%20still%20only%20contains%20the%20%60left%60%20value%20or%20the%20%60right%60%20value.%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_(B%2C%20Bifunctor%2C%20Callable%2C%20D%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20BiEither%5BA%2C%20C%5D(Bifunctor)%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%20C%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%20raise%20TypeError(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%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%20)%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20bimap(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20h%3A%20Callable%5B%5BC%5D%2C%20D%5D%2C%20fa%3A%20%22BiEither%5BA%2C%20C%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22BiEither%5BB%2C%20D%5D%22%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%3Dg(fa.left))%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls(right%3Dh(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(BiEither%2C)%0A%0A%0A%40app.cell%0Adef%20_(BiEither)%3A%0A%20%20%20%20print(BiEither.bimap(lambda%20x%3A%20x%20%2B%201%2C%20lambda%20x%3A%20x%20*%202%2C%20BiEither(left%3D1)))%0A%20%20%20%20print(BiEither.bimap(lambda%20x%3A%20x%20%2B%201%2C%20lambda%20x%3A%20x%20*%202%2C%20BiEither(right%3D2)))%0A%20%20%20%20print(BiEither.first(lambda%20x%3A%20x%20%2B%201%2C%20BiEither(left%3D1)))%0A%20%20%20%20print(BiEither.first(lambda%20x%3A%20x%20%2B%201%2C%20BiEither(right%3D2)))%0A%20%20%20%20print(BiEither.second(lambda%20x%3A%20x%20%2B%201%2C%20BiEither(left%3D1)))%0A%20%20%20%20print(BiEither.second(lambda%20x%3A%20x%20%2B%201%2C%20BiEither(right%3D2)))%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%202d%20Tuple%20Bifunctor%0A%0A%20%20%20%20%20%20%20%20For%202d%20tuples%2C%20we%20simply%20expect%20%60bimap%60%20to%20map%202%20functions%20to%20the%202%20elements%20in%20the%20tuple%20respectively.%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_(B%2C%20Bifunctor%2C%20Callable%2C%20D%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20BiTuple%5BA%2C%20C%5D(Bifunctor)%3A%0A%20%20%20%20%20%20%20%20value%3A%20tuple%5BA%2C%20C%5D%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20bimap(%0A%20%20%20%20%20%20%20%20%20%20%20%20cls%2C%20g%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20h%3A%20Callable%5B%5BC%5D%2C%20D%5D%2C%20fa%3A%20%22BiTuple%5BA%2C%20C%5D%22%0A%20%20%20%20%20%20%20%20)%20-%3E%20%22BiTuple%5BB%2C%20D%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20cls((g(fa.value%5B0%5D)%2C%20h(fa.value%5B1%5D)))%0A%20%20%20%20return%20(BiTuple%2C)%0A%0A%0A%40app.cell%0Adef%20_(BiTuple)%3A%0A%20%20%20%20print(BiTuple.bimap(lambda%20x%3A%20x%20%2B%201%2C%20lambda%20x%3A%20x%20*%202%2C%20BiTuple((1%2C%202))))%0A%20%20%20%20print(BiTuple.first(lambda%20x%3A%20x%20%2B%201%2C%20BiTuple((1%2C%202))))%0A%20%20%20%20print(BiTuple.second(lambda%20x%3A%20x%20%2B%201%2C%20BiTuple((1%2C%202))))%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%20Bifunctor%20laws%0A%0A%20%20%20%20%20%20%20%20The%20only%20law%20we%20need%20to%20follow%20is%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20bimap(id%2C%20id%2C%20fa)%20%3D%3D%20id(fa)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20and%20then%20other%20laws%20are%20followed%20automatically.%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_(BiEither%2C%20BiTuple%2C%20id)%3A%0A%20%20%20%20print(BiEither.bimap(id%2C%20id%2C%20BiEither(left%3D1))%20%3D%3D%20id(BiEither(left%3D1)))%0A%20%20%20%20print(BiEither.bimap(id%2C%20id%2C%20BiEither(right%3D1))%20%3D%3D%20id(BiEither(right%3D1)))%0A%20%20%20%20print(BiTuple.bimap(id%2C%20id%2C%20BiTuple((1%2C%202)))%20%3D%3D%20id(BiTuple((1%2C%202))))%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%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Further%20reading%0A%0A%20%20%20%20%20%20%20%20-%20%5BThe%20Trivial%20Monad%5D(http%3A%2F%2Fblog.sigfpe.com%2F2007%2F04%2Ftrivial-monad.html)%0A%20%20%20%20%20%20%20%20-%20%5BHaskellforall%3A%20The%20Category%20Design%20Pattern%5D(https%3A%2F%2Fwww.haskellforall.com%2F2012%2F08%2Fthe-category-design-pattern.html)%0A%20%20%20%20%20%20%20%20-%20%5BHaskellforall%3A%20The%20Functor%20Design%20Pattern%5D(https%3A%2F%2Fwww.haskellforall.com%2F2012%2F09%2Fthe-functor-design-pattern.html)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%2F%20attention%20%7C%20ATTENTION%20%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20functor%20design%20pattern%20doesn't%20work%20at%20all%20if%20you%20aren't%20using%20categories%20in%20the%20first%20place.%20This%20is%20why%20you%20should%20structure%20your%20tools%20using%20the%20compositional%20category%20design%20pattern%20so%20that%20you%20can%20take%20advantage%20of%20functors%20to%20easily%20mix%20your%20tools%20together.%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20-%20%5BHaskellwiki%3A%20Functor%5D(https%3A%2F%2Fwiki.haskell.org%2Findex.php%3Ftitle%3DFunctor)%0A%20%20%20%20%20%20%20%20-%20%5BHaskellwiki%3A%20Typeclassopedia%23Functor%5D(https%3A%2F%2Fwiki.haskell.org%2Findex.php%3Ftitle%3DTypeclassopedia%23Functor)%0A%20%20%20%20%20%20%20%20-%20%5BHaskellwiki%3A%20Typeclassopedia%23Category%5D(https%3A%2F%2Fwiki.haskell.org%2Findex.php%3Ftitle%3DTypeclassopedia%23Category)%0A%20%20%20%20%20%20%20%20-%20%5BHaskellwiki%3A%20Category%20Theory%5D(https%3A%2F%2Fen.wikibooks.org%2Fwiki%2FHaskell%2FCategory_theory)%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_()%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%20abstractmethod%2C%20ABC%0A%20%20%20%20return%20ABC%2C%20abstractmethod%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20from%20dataclasses%20import%20dataclass%0A%20%20%20%20from%20typing%20import%20Callable%2C%20TypeVar%2C%20Union%0A%20%20%20%20from%20pprint%20import%20pp%0A%20%20%20%20return%20Callable%2C%20TypeVar%2C%20Union%2C%20dataclass%2C%20pp%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%20D%20%3D%20TypeVar(%22D%22)%0A%20%20%20%20return%20A%2C%20B%2C%20C%2C%20D%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A