Category Theory and Functors

import%20marimo%0A%0A__generated_with%20%3D%20%220.12.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.1%20%7C%20last%20modified%3A%202025-03-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%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%20Callable%2C%20Generic%2C%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(Generic%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%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(Functor%2C%20Generic%5BA%5D)%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%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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(f(a.value))%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%20apply%20transformations%20without%20unwrapping%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%3E%3E%3E%20Wrapper.fmap(lambda%20x%3A%20x%20%2B%201%2C%20wrapper)%0A%20%20%20%20%20%20%20%20Wrapper(value%3D2)%0A%0A%20%20%20%20%20%20%20%20%3E%3E%3E%20Wrapper.fmap(lambda%20x%3A%20%5Bx%5D%2C%20wrapper)%0A%20%20%20%20%20%20%20%20Wrapper(value%3D%5B1%5D)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20%3E%20Try%20using%20the%20%60Wrapper%60%20in%20the%20cell%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%20Callable%2C%20Functor%2C%20Generic%2C%20dataclass%2C%20pp)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Wrapper(Functor%2C%20Generic%5BA%5D)%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%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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(f(a.value))%0A%0A%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%20Wrapper%2C%20wrapper%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%60f%60%20is%20of%20type%20%60Callable%5B%5BA%5D%2C%20B%5D%60%0A%20%20%20%20%20%20%20%20*%20%60a%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(f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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%20Wrapper%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%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%20List(Functor%2C%20Generic%5BA%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20value%3A%20list%5BA%5D%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%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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%20%20%20%20%20return%20List(%5Bf(x)%20for%20x%20in%20a.value%5D)%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%20apply%20transformations%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%3E%3E%3E%20flist%20%3D%20List(%5B1%2C%202%2C%203%2C%204%5D)%0A%20%20%20%20%20%20%20%20%3E%3E%3E%20List.fmap(lambda%20x%3A%20x%20%2B%201%2C%20flist)%0A%20%20%20%20%20%20%20%20List(value%3D%5B2%2C%203%2C%204%2C%205%5D)%0A%20%20%20%20%20%20%20%20%3E%3E%3E%20List.fmap(lambda%20x%3A%20%5Bx%5D%2C%20flist)%0A%20%20%20%20%20%20%20%20List(value%3D%5B%5B1%5D%2C%20%5B2%5D%2C%20%5B3%5D%2C%20%5B4%5D%5D)%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%0Adef%20_(A%2C%20B%2C%20Callable%2C%20Functor%2C%20Generic%2C%20dataclass%2C%20pp)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20List(Functor%2C%20Generic%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%40classmethod%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%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(%5Bf(x)%20for%20x%20in%20a.value%5D)%0A%0A%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%20List%2C%20flist%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(f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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(f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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(f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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%20from%20dataclasses%20import%20dataclass%0A%20%20%20%20%20%20%20%20from%20typing%20import%20Callable%2C%20Generic%2C%20TypeVar%0A%20%20%20%20%20%20%20%20from%20abc%20import%20ABC%2C%20abstractmethod%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%20Functor(ABC%2C%20Generic%5BA%5D)%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(f%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%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%0A%20%20%20%20%20%20%20%20Next%2C%20let's%20implement%20a%20more%20complex%20data%20structure%3A%20%5BRoseTree%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FRose_tree).%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%20Case%20Study%3A%20RoseTree%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%20We%20can%20implement%20%60RoseTree%60%20by%20extending%20the%20%60Functor%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%20Callable%2C%20Generic%2C%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%20RoseTree(Functor%2C%20Generic%5Ba%5D)%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20value%3A%20A%0A%20%20%20%20%20%20%20%20%20%20%20%20children%3A%20list%5B%22RoseTree%5BA%5D%22%5D%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%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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%20%20%20%20return%20RoseTree(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f(a.value)%2C%20%5Bcls.fmap(f%2C%20child)%20for%20child%20in%20a.children%5D%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%20%20%20%20def%20__repr__(self)%20-%3E%20str%3A%0A%20%20%20%20%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%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20The%20function%20is%20applied%20**recursively**%20to%20each%20node's%20value.%0A%20%20%20%20%20%20%20%20-%20The%20tree%20structure%20**remains%20unchanged**.%0A%20%20%20%20%20%20%20%20-%20Only%20the%20values%20inside%20the%20tree%20are%20modified.%0A%0A%20%20%20%20%20%20%20%20%3E%20Try%20using%20%60RoseTree%60%20in%20the%20cell%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(hide_code%3DTrue)%0Adef%20_(A%2C%20B%2C%20Callable%2C%20Functor%2C%20Generic%2C%20dataclass%2C%20mo)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20RoseTree(Functor%2C%20Generic%5BA%5D)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Doc%3A%20RoseTree%0A%0A%20%20%20%20%20%20%20%20A%20Functor%20implementation%20of%20%60RoseTree%60%2C%20allowing%20transformation%20of%20values%20while%20preserving%20the%20tree%20structure.%0A%0A%20%20%20%20%20%20%20%20**Attributes**%0A%0A%20%20%20%20%20%20%20%20-%20%60value%20(A)%60%3A%20The%20value%20stored%20in%20the%20node.%0A%20%20%20%20%20%20%20%20-%20%60children%20(list%5BRoseTree%5BA%5D%5D)%60%3A%20A%20list%20of%20child%20nodes%20forming%20the%20tree%20structure.%0A%0A%20%20%20%20%20%20%20%20**Methods%3A**%0A%0A%20%20%20%20%20%20%20%20-%20%60fmap(f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%3A%20%22RoseTree%5BA%5D%22)%20-%3E%20%22RoseTree%5BB%5D%22%60%0A%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**Implementation%20logic%3A**%0A%0A%20%20%20%20%20%20%20%20%20%20-%20The%20function%20%60f%60%20is%20applied%20to%20the%20root%20node's%20%60value%60.%0A%20%20%20%20%20%20%20%20%20%20-%20Each%20child%20in%20%60children%60%20recursively%20calls%20%60fmap%60%2C%20ensuring%20all%20values%20in%20the%20tree%20are%20mapped.%0A%20%20%20%20%20%20%20%20%20%20-%20The%20overall%20tree%20structure%20remains%20unchanged.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%0A%20%20%20%20%20%20%20%20value%3A%20A%0A%20%20%20%20%20%20%20%20children%3A%20list%5B%22RoseTree%5BA%5D%22%5D%0A%0A%20%20%20%20%20%20%20%20%40classmethod%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%22RoseTree%5BA%5D%22)%20-%3E%20%22RoseTree%5BB%5D%22%3A%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%20f(a.value)%2C%20%5Bcls.fmap(f%2C%20child)%20for%20child%20in%20a.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%0A%0A%20%20%20%20mo.md(RoseTree.__doc__)%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(func%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%20We%20can%20implement%20a%20similar%20idea%20in%20Python%3A%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%20f%2C%20functor%3A%20functor.__class__.fmap(f%2C%20functor)%0A%20%20%20%20%20%20%20%20inc%20%3D%20lambda%20functor%3A%20fmap(lambda%20x%3A%20x%20%2B%201%2C%20functor)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20-%20**%60fmap%60**%3A%20Lifts%20an%20ordinary%20function%20(%60f%60)%20to%20the%20functor%20world%2C%20allowing%20the%20function%20to%20operate%20on%20the%20wrapped%20value%20inside%20the%20functor.%0A%20%20%20%20%20%20%20%20-%20**%60inc%60**%3A%20A%20specific%20instance%20of%20%60fmap%60%20that%20operates%20on%20any%20functor.%20It%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%0A%20%20%20%20%20%20%20%20Thus%2C%20**%60fmap%60**%20transforms%20an%20ordinary%20function%20into%20a%20**function%20that%20operates%20on%20functors**%2C%20and%20**%60inc%60**%20is%20a%20specific%20case%20where%20it%20increments%20the%20value%20inside%20the%20functor.%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20Applying%20the%20%60inc%60%20Function%20to%20Various%20Functors%0A%0A%20%20%20%20%20%20%20%20You%20can%20now%20apply%20%60inc%60%20to%20any%20functor%20like%20%60Wrapper%60%2C%20%60List%60%2C%20or%20%60RoseTree%60%3A%0A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%23%20Applying%20%60inc%60%20to%20a%20Wrapper%0A%20%20%20%20%20%20%20%20wrapper%20%3D%20Wrapper(5)%0A%20%20%20%20%20%20%20%20inc(wrapper)%20%20%23%20Wrapper(value%3D6)%0A%0A%20%20%20%20%20%20%20%20%23%20Applying%20%60inc%60%20to%20a%20List%0A%20%20%20%20%20%20%20%20list_wrapper%20%3D%20List(%5B1%2C%202%2C%203%5D)%0A%20%20%20%20%20%20%20%20inc(list_wrapper)%20%20%23%20List(value%3D%5B2%2C%203%2C%204%5D)%0A%0A%20%20%20%20%20%20%20%20%23%20Applying%20%60inc%60%20to%20a%20RoseTree%0A%20%20%20%20%20%20%20%20tree%20%3D%20RoseTree(1%2C%20%5BRoseTree(2%2C%20%5B%5D)%2C%20RoseTree(3%2C%20%5B%5D)%5D)%0A%20%20%20%20%20%20%20%20inc(tree)%20%20%23%20RoseTree(value%3D2%2C%20children%3D%5BRoseTree(value%3D3%2C%20children%3D%5B%5D)%2C%20RoseTree(value%3D4%2C%20children%3D%5B%5D)%5D)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20%3E%20Try%20using%20%60fmap%60%20in%20the%20cell%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_(flist%2C%20pp%2C%20rosetree%2C%20wrapper)%3A%0A%20%20%20%20fmap%20%3D%20lambda%20f%2C%20functor%3A%20functor.__class__.fmap(f%2C%20functor)%0A%20%20%20%20inc%20%3D%20lambda%20functor%3A%20fmap(lambda%20x%3A%20x%20%2B%201%2C%20functor)%0A%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%20fmap%2C%20inc%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%20automatically%20satisfy%20the%20%5Bsecond%20law%5D(https%3A%2F%2Fgithub.com%2Fquchen%2Farticles%2Fblob%2Fmaster%2Fsecond_functor_law.mo)%20as%20well.%0A%20%20%20%20%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20Functor%20Law%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%20below%3A%0A%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%20add%20a%20helper%20function%20%60check_functor_law%60%20to%20verify%20that%20an%20instance%20satisfies%20the%20functor%20laws.%0A%0A%20%20%20%20%20%20%20%20%60%60%60Python%0A%20%20%20%20%20%20%20%20check_functor_law%20%3D%20lambda%20functor%3A%20repr(fmap(id%2C%20functor))%20%3D%3D%20repr(functor)%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20We%20can%20verify%20the%20functor%20we've%20defined.%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%20compose%2C%20id%0A%0A%0A%40app.cell%0Adef%20_(fmap%2C%20id)%3A%0A%20%20%20%20check_functor_law%20%3D%20lambda%20functor%3A%20repr(fmap(id%2C%20functor))%20%3D%3D%20repr(functor)%0A%20%20%20%20return%20(check_functor_law%2C)%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%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%20And%20here%20is%20an%20%60EvilFunctor%60.%20We%20can%20verify%20it's%20not%20a%20valid%20%60Functor%60.%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%20EvilFunctor(Functor%2C%20Generic%5BA%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20value%3A%20list%5BA%5D%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%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%3A%20%22EvilFunctor%5BA%5D%22)%20-%3E%20%22EvilFunctor%5BB%5D%22%3A%0A%20%20%20%20%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%20%20%20%20%20cls(%5Ba.value%5B0%5D%5D%20*%202%20%2B%20list(map(f%2C%20a.value%5B1%3A%5D)))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20a.value%0A%20%20%20%20%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%20%20%20%20)%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%0Adef%20_(A%2C%20B%2C%20Callable%2C%20Functor%2C%20Generic%2C%20check_functor_law%2C%20dataclass%2C%20pp)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20EvilFunctor(Functor%2C%20Generic%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%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%20a%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(%5Ba.value%5B0%5D%5D%20*%202%20%2B%20%5Bf(x)%20for%20x%20in%20a.value%5B1%3A%5D%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20a.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%0A%0A%20%20%20%20pp(check_functor_law(EvilFunctor(%5B1%2C%202%2C%203%2C%204%5D)))%0A%20%20%20%20return%20(EvilFunctor%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%20Final%20definition%20of%20Functor%0A%0A%20%20%20%20%20%20%20%20We%20can%20now%20draft%20the%20final%20definition%20of%20%60Functor%60%20with%20some%20utility%20functions.%0A%0A%20%20%20%20%20%20%20%20%60%60%60Python%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(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%20%20%20%20%20return%20NotImplementedError%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%20const_fmap(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%20%20%20%20%20return%20cls.fmap(lambda%20_%3A%20b%2C%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%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%20%20%20%20%20return%20cls.const_fmap(a%2C%20None)%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_(A%2C%20ABC%2C%20B%2C%20Callable%2C%20Generic%2C%20abstractmethod%2C%20dataclass%2C%20mo)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Functor(ABC%2C%20Generic%5BA%5D)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Doc%3A%20Functor%0A%0A%20%20%20%20%20%20%20%20A%20generic%20interface%20for%20types%20that%20support%20mapping%20over%20their%20values.%0A%0A%20%20%20%20%20%20%20%20**Methods%3A**%0A%0A%20%20%20%20%20%20%20%20-%20%60fmap(f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%3A%20Functor%5BA%5D)%20-%3E%20Functor%5BB%5D%60%0A%20%20%20%20%20%20%20%20%20%20Abstract%20method%20to%20apply%20a%20function%20to%20all%20values%20inside%20a%20functor.%0A%0A%20%20%20%20%20%20%20%20-%20%60const_fmap(a%3A%20%22Functor%5BA%5D%22%2C%20b%3A%20B)%20-%3E%20Functor%5BB%5D%60%0A%20%20%20%20%20%20%20%20%20%20Replaces%20all%20values%20inside%20a%20functor%20with%20a%20constant%20%60b%60%2C%20preserving%20the%20original%20structure.%0A%0A%20%20%20%20%20%20%20%20-%20%60void(a%3A%20%22Functor%5BA%5D%22)%20-%3E%20Functor%5BNone%5D%60%0A%20%20%20%20%20%20%20%20%20%20Equivalent%20to%20%60const_fmap(a%2C%20None)%60%2C%20transforming%20all%20values%20in%20a%20functor%20into%20%60None%60.%0A%20%20%20%20%20%20%20%20%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%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%20return%20NotImplementedError%0A%0A%20%20%20%20%20%20%20%20%40classmethod%0A%20%20%20%20%20%20%20%20def%20const_fmap(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%0A%0A%20%20%20%20mo.md(Functor.__doc__)%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(%22%22%22%3E%20Try%20with%20utility%20functions%20in%20the%20cell%20below%22%22%22)%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_fmap(rosetree%2C%20%22%CE%BB%22))%0A%20%20%20%20pp(RoseTree.void(rosetree))%0A%20%20%20%20pp(List.const_fmap(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(%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Functors%20for%20Non-Iterable%20Types%0A%0A%20%20%20%20%20%20%20%20In%20the%20previous%20examples%2C%20we%20implemented%20functors%20for%20**iterables**%2C%20like%20%60List%60%20and%20%60RoseTree%60%2C%20which%20are%20inherently%20**iterable%20types**.%20This%20is%20a%20natural%20fit%20for%20functors%2C%20as%20iterables%20can%20be%20mapped%20over.%0A%0A%20%20%20%20%20%20%20%20However%2C%20**functors%20are%20not%20limited%20to%20iterables**.%20There%20are%20cases%20where%20we%20want%20to%20apply%20the%20concept%20of%20functors%20to%20types%20that%20are%20not%20inherently%20iterable%2C%20such%20as%20types%20that%20represent%20optional%20values%2C%20computations%2C%20or%20other%20data%20structures.%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20The%20Maybe%20Functor%0A%0A%20%20%20%20%20%20%20%20One%20example%20is%20the%20**%60Maybe%60**%20type%20from%20Haskell%2C%20which%20is%20used%20to%20represent%20computations%20that%20can%20either%20result%20in%20a%20value%20or%20no%20value%20(%60Nothing%60).%20%0A%0A%20%20%20%20%20%20%20%20We%20can%20define%20the%20%60Maybe%60%20functor%20as%20below%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%20Maybe(Functor%2C%20Generic%5BA%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20value%3A%20None%20%7C%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%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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%20%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cls(None)%20if%20a.value%20is%20None%20else%20cls(f(a.value))%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%20%20%20%20def%20__repr__(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20%22Nothing%22%20if%20self.value%20is%20None%20else%20repr(self.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%0Adef%20_(A%2C%20B%2C%20Callable%2C%20Functor%2C%20Generic%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Maybe(Functor%2C%20Generic%5BA%5D)%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%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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%20a.value%20is%20None%20else%20cls(f(a.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%20repr(self.value)%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(%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20**%60Maybe%60**%20is%20a%20functor%20that%20can%20either%20hold%20a%20value%20or%20be%20%60Nothing%60%20(equivalent%20to%20%60None%60%20in%20Python).%20The%20%60fmap%60%20method%20applies%20a%20function%20to%20the%20value%20inside%20the%20functor%2C%20if%20it%20exists.%20If%20the%20value%20is%20%60None%60%20(representing%20%60Nothing%60)%2C%20%60fmap%60%20simply%20returns%20%60None%60.%0A%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%0A%20%20%20%20%20%20%20%20%3E%20Try%20using%20%60Maybe%60%20in%20the%20cell%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_(Maybe%2C%20pp)%3A%0A%20%20%20%20mint%20%3D%20Maybe(1)%0A%20%20%20%20mnone%20%3D%20Maybe(None)%0A%0A%20%20%20%20pp(Maybe.fmap(lambda%20x%3A%20x%20%2B%201%2C%20mint))%0A%20%20%20%20pp(Maybe.fmap(lambda%20x%3A%20x%20%2B%201%2C%20mnone))%0A%20%20%20%20return%20mint%2C%20mnone%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%20Generic%5BA%5D)%20-%3E%20Generic%5BA%5D%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(ABC%2C%20Generic%5BA%5D)%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(Functor%2C%20Generic%5BA%5D)%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%2C%20i.e.%3A%20%24%7B%5Cdisplaystyle%20F(%5Coperatorname%20%7Bid%7D%20_%7BA%7D)%3D%5Coperatorname%20%7Bid%7D%20_%7BF(A)%7D%7D%24%0A%20%20%20%20%20%20%20%202.%20Functors%20must%20distribute%20over%20morphism%20composition%2C%20i.e.%20%24%7B%5Cdisplaystyle%20F(f%5Ccirc%20g)%3DF(f)%5Ccirc%20F(g)%7D%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%60fmap%60%2C%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%20fmap%20%3D%20lambda%20f%2C%20functor%3A%20functor.__class__.fmap(f%2C%20functor)%20%20%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%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%20**Notice%20that**%20in%20this%20case%2C%20we%20can%20actually%20view%20%60fmap%60%20as%3A%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20fmap%20%3D%20lambda%20f%2C%20functor%3A%20functor.fmap(f%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%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(Functor%2C%20Generic%5BA%5D)%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%20f%3A%20Callable%5B%5BA%5D%2C%20B%5D%2C%20a%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(f(a.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%20fmap%2C%20id%2C%20pp%2C%20wrapper)%3A%0A%20%20%20%20pp(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%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%20ListConcatenation(Generic%5BA%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20value%3A%20list%5BA%5D%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%20id()%20-%3E%20%22ListConcatenation%5BA%5D%22%3A%0A%20%20%20%20%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%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%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%20%20%20)%20-%3E%20%22ListConcatenation%5Ba%5D%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20ListConcatenation(this.value%20%2B%20other.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%0Adef%20_(A%2C%20Generic%2C%20dataclass)%3A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20ListConcatenation(Generic%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%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%20IntAddition%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20value%3A%20int%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%20id()%20-%3E%20%22IntAddition%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20IntAddition(0)%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(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%20%20%20%20%20return%20IntAddition(this.value%20%2B%20other.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%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%23%23%23%23%201.%20**Identity%20Law**%3A%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%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%3E%20length(ListConcatenation.id())%20%3D%3D%20IntAddition.id()%0A%20%20%20%20%20%20%20%20True%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(%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%23%23%23%23%202.%20**Composition%20Law**%3A%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%0A%20%20%20%20%20%20%20%20%60%60%60python%0A%20%20%20%20%20%20%20%20%3E%20lista%20%3D%20ListConcatenation(%5B1%2C%202%5D)%0A%20%20%20%20%20%20%20%20%3E%20listb%20%3D%20ListConcatenation(%5B3%2C%204%5D)%0A%20%20%20%20%20%20%20%20%3E%20length(ListConcatenation.compose(lista%2C%20listb))%20%3D%3D%20IntAddition.compose(%0A%20%20%20%20%20%20%20%20%3E%20%20%20%20%20length(lista)%2C%20length(listb)%0A%20%20%20%20%20%20%20%20%3E%20)%0A%20%20%20%20%20%20%20%20True%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(%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%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%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%20lista%2C%20listb%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%5BHaskellwiki.%20Category%20Theory%5D(https%3A%2F%2Fen.wikibooks.org%2Fwiki%2FHaskell%2FCategory_theory)%0A%20%20%20%20%20%20%20%20-%20%5BHaskellforall.%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.%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.%20Functor%5D(https%3A%2F%2Fwiki.haskell.org%2Findex.php%3Ftitle%3DFunctor)%0A%20%20%20%20%20%20%20%20-%20%5BHaskellwiki.%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.%20Typeclassopedia%23Category%5D(https%3A%2F%2Fwiki.haskell.org%2Findex.php%3Ftitle%3DTypeclassopedia%23Category)%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%20Generic%2C%20TypeVar%0A%20%20%20%20from%20pprint%20import%20pp%0A%20%20%20%20return%20Callable%2C%20Generic%2C%20TypeVar%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%20return%20A%2C%20B%2C%20C%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A