9 ความเป็นFunctor (Draft)
ในตอนนี้คุณได้รู้ว่าfunctorคืออะไรและได้เห็นตัวอย่างต่างๆของมัน เรามาดูวิธีในการสร้างfunctorที่ใหญ่กว่าจากตัวเล็กๆ มันนั้นน่าสนใจโดยเฉพาะเช่นการที่จะเห็นconstructorของtype(ที่คือการโยงระหว่างวัตถุในcategory) สามารถถูกเสริมเติมให้เป็นfunctor(ที่รวมไปภึงการโยงระหว่างmorphism)
9.1 Bifunctors
เนื่องด้วยว่าfunctorsคือmorphismใน\(\textbf{Cat}\)(categoryของcategory)ความเข้าใจหลายๆอย่างที่เกี่ยวกับmorphism (และfunctionโดยเฉพาะ) ก็สามารถถูกใช้ได้กับfunctorsเช่นเดียวกัน ตัวอย่างเช่นเดียวกันกับการที่คุณมีfunctionที่มีสองargument คุณสามารถที่จะมีfunctorที่มีสองargumentหรือbifunctor ถ้าพูดถึงการกระทำบนวัตถุ bifunctorนั้นโยงทุกๆคู่ของวัตถุอันหนึ่งจากcategory\(\textbf{C}\)และวัตถุจากcategory\(\textbf{D}\) ไปยังวัตถุในcategory\(\textbf{E}\) สังเกตได้ว่าสิ่งนี้ก็แค่คือการโยงจากการคูณแบบCartesian ของcategoryอย่าง\(\textbf{C}\times\textbf{D}\)ไปยัง\(\textbf{E}\)
สิ่งนี้ค่อนข้างตรงไปตรงมา แต่ความเป็นfunctorหมายความว่า bifunctorต้องทำการโยงmorphismเช่นเดียวกัน แต่ในตอนนี้มันต้องโยงคู่ของmorphismที่ตัวหนึ่งมาจาก\(\textbf{C}\) และตัวหนึ่งมาจาก\(\textbf{D}\)ไปยังmorphismใน\(\textbf{E}\)
อีกครั้งว่าคู่ของmorphismคือแค่morphismเดี่ยวในproduct category \(\textbf{C}\times\textbf{D}\)ไปยัง\(\textbf{E}\) เรานิยามmorphismในการคูณแบบCartesianของcategoryต่างๆในฐานะคู่ของmorphismที่เริ่มจากคู่แรกของวัตถุไปยังอีกคู่หนึ่งของวัตถุ คู่morphismเหล่านี้สามารถถูกประกอบในวิธีที่ตรงไปตรงมา
\[ (f, g) \circ (f', g') = (f \circ f', g \circ g') \]
การประกอบแบบนี้นั้นมีคุณสมบัติการเปลี่ยนหมู่และมันมีidentity(คู่ของidentity morphismอย่าง \((\operatorname{id}, \operatorname{id})\)) ดังนั้นคูณแบบCartesianของcategoryก็เป็นcategory
วิธีที่ง่ายกว่าในการคิดเกี่ยวกับbifunctorก็คงจะเป็นการพิจารณามันในแต่ละargumentแยกออกไป ดังนั้นแทนที่จะแปลฏทางfunctor (การรักษาสมบัติการเปลี่ยนหมู่และidentity) จากfunctorไปยังbifunctor มันดีพอที่จะทดสอบมันโดยการแยกออกเป็นที่ละargument แต่โดยทั่วไปแล้ว ความเป็นfunctorแบบแยกๆไม่สามารถที่จะพิสูจน์ความเป็นfunctorทั้งหมด categoryที่ไม่ความเป็นfunctorแบบทั้งหมด จะถูกเรียกว่าpremonoidal
เรามานิยามbifunctorในHaskell ในกรณีนี้ทั้งสามcategoryนั้นเหมือนกันนั้นก็คือcategoryของtypeในHaskell bifuntorคือconstructorของtypeที่นำสองargumentของtypeเข้ามา นี่คือนิยามของBifunctortypeclassที่เอามาโดยตรงจากlibaryControl.Bifunctor
class Bifunctor f where
bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
bimap g h = first g . second h
first :: (a -> c) -> f a b -> f c b
first g = bimap g id
second :: (b -> d) -> f a b -> f a d
second = bimap id
ต้วแปรของtypefแทนbifunctionนี้ คุณสามารถที่จะเห็นได้ว่าในtype signatureต่างๆนี้ถูกนำไปใช้กับสองargumentของtype ในtype signatureแรกนิยามbimapที่คือการโยงสองfunctionในเวลาเดียวกัน ผลที่ตามมาคือfunctionที่ถูกliftf a -> f c d ที่กระทำบนtypeที่ถูกสร้างโดยconstructorของbifunction type ได้มีการเขียนของbimapในรูปแบบของfirstและsecond (เป็นดั่งที่กล่าวก่อนหน้านี้ว่ามันไม่ได้ใช้ได้ตลอดเพราะว่าการโยงทั้งสองอาจจะไม่สามารถสลับที่ได้ นั่นก็คือfirst g . second hอาจจะไม่เหมือนกับsecond h . first g)
ในtype signatureทั้งสองที่เหลือfirstและsecondคือfmaps ทั้งสองเป็นตัวแทนของความเป็นfunctorของfในargumentตัวแรกและตัวที่สองตามลำดับ
นิยามของtype classนี้ให้การเขียนมาอยู่แล้วของทั้งสอง(firstและsecond)ในรูปแบบของbimap
ในตอนประกาศinstanceของBifunctorคุณมีทางเลือกของการเขียนbimapและยอบรับกับการเขียนที่ให้มาอยู่แล้วของสำหรับfirstและsecond หรือการเขียนทั้งfirstและsecondและยอมรับบการเขียนที่ให้มาอยู่แล้วของสำหรับbimap (แน่นอนว่าคุณอาจจะเขียนทั้งสามตัวหมดแต่มันก็ขึ้นอยู่กับคุณที่จะทำให้แน่ใจว่าพวกมันมีความเกี่ยวข้องในแบบที่จำเป็น)
9.2 BifunctorแบบProductและCoproduct
ตัวอย่างที่ดีที่สุดของbifunctorคือproductแบบcategory (productของสองวัตถุที่ถูกนิยามโดยการสร้างแบบสากล) ถ้าproductนั้นมีอยู่สำหรับทุกๆคู่ของวัตถุ การโยงจากวัตถุเหล่านี้ไปยังproductนั้นก็มีความเป็นbifunctor มันเป็นจริงโดยทั่วไปและโดยเฉพาะHaskell ในที่นี้instanceBifunctorสำหรับconstructorแบบpair ที่เป็นtypeแบบproductที่เรียบง่ายที่สุด
instance Bifunctor (,) where
bimap f g (x, y) = (f x, g y)มันไม่มีตัวเลือกอื่นๆbimapนั้นแค่นำfunctionแรกไปใช้กับส่วนแรกและfunctionที่สองไปใช้กับส่วนที่สอง โค้ดของสิ่งนี้เขียนตัวมันเองอยู่แล้วถ้าให้typesต่างๆกับมัน
bimap :: (a -> c) -> (b -> d) -> (a, b) -> (c, d)การกระทำของbifunctorในที่นี้คือการทำpairของtypeตัวอย่างเช่น
(,) a b = (a, b)โดยduality coproductถ้ามันสามารถถูกนิยามสำหรับทุกๆคู่ของวัตถุในcategoryก็คือbifucntorเช่นกัน ในHaskellนี้ถูกแสดงโดยconstructorของtypeEitherซึ่งก็เป็นinstanceของBifunctor
instance Bifunctor Either where
bimap f _ (Left x) = Left (f x)
bimap _ g (Right y) = Right (g y)โค้ดของสิ่งนี้ก็เขียนตัวมันเองเช่นกัน
ในตอนนี้เรายังจำตอนที่เราพูดเกี่ยวกับcategoryที่เป็นแบบmonoidได้หรือเปล่า? categoryแบบmonoidนิยามoperatorที่เป็นbinaryในการกระทำกับคู่ของวัตถุกับวัตถุที่เป็นunit ผมได้เอ่ยถึงว่า\(\textbf{Set}\)นั้นเป็นcategoryแบบmonoidเมื่อมีการคูณแบบCartesianคู่กับsetที่มีสมาชิกเดี่ยวที่มีฐานะเป็นunit สิ่งที่ผมไม่ได้กล่าวถึงคือว่าหนึ่งในเงื่อนไขสำหรับoperator binaryคือว่ามันต้องเป็นbifunctor นี่คือเงื่อนไขที่สำคัญ เราต้องการproductแบบmonoidให้เข้ากันได้กับโครงสร้างของcategoryที่ที่ถูกนิยามโดยmorphism เรานั้นเข้าใกล้ถึงนิยามเต็มของcategoryแบบmonoidไปอีกขั้น (เรายังต้องเราเกี่ยวกับnaturality(ความเป็นธรรมชาติ)ก่อนที่จะไปถึงจุดนั้น)
9.3 typeข้อมูลแบบพีชคณิตที่มีความเป็นfunctor (Functorial Algebraic Data Types)
เราได้เห็นตัวอย่างหลายๆตัวของtypeข้อมูลที่ถูกparameterizedที่กลายมาเป็นfunctor เราสามารถที่จะนิยามfmapสำหรับมัน typeข้อมูลที่มีความชับช้อนนั้นถูกสร้างจากtypeข้อมูลที่ง่ายกว่า โดยเฉพาะtypeข้อมูลแบบพีชคณิต(algebraic data types (ADTs))ที่ถูกสร้างโดยการใช้sumและproduct เราได้เห็นมาแล้วว่าsumและproductนั้นมีความเป็นfunctor และเราก็รู้ว่าfunctorสามารถประกอบกันได้ ดังนั้นถ้าเราสามารถที่จะแสดงได้ว่าส่วนประกอบของADTsนั้นมีความเป็นfunctor เราก็จะรู้ได้ว่าADTที่ถูกparameterizedนั้นก็มีความเป็นfunctorเช่นกัน
ดังนั้นอะไรคือส่วนประกอบของADTsที่ถูกparameterized? อย่างแรกได้มีส่วนที่ไม่ขึ้นกับparameterของtypeของfunctorอย่าง NothingในMaybeหรือNilในList พวกมันมีความเท่ากันกับfunctorConst โดยที่functorConstนั้นไม่สนใจparameterของtype (จริงๆแล้วparameterของtypeที่สองคือเป็นสิ่งที่เราสนใจ และตัวแรกก็ถูกเก็บไว้ให้คงที่)
ดังนั้นมันก็จะมีส่วนที่แค่ครอบ(encapsulate)parameterของtypeในมันเองเหมือนกับJustในMaybe มันนั้นเท่ากันกับfunctorที่เป็นidentity ผมได้กล่าวถึงfunctorที่เป็นidentityไปก่อนหน้านี้ในฐานะmorphismที่เป็นidentityใน\(\textbf{Cat}\)แต่ไม่ได้ให้นิยามของมันในHaskellให้ชัดเจน นี่คือนิยามของมัน
data Identity a = Identity ainstance Functor Identity where
fmap f (Identity x) = Identity (f x)คุณสามารถที่จะคิดถึงIdentityในฐานะcontainerที่เรียบง่ายที่สุดที่ก็จะเก็บแค่ค่า(ที่ไม่สามารถเปลี่ยนได้)ของtypea
ทุกๆอย่างที่่เหลือในdata structureแบบพีชคณิตนั้นสร้างมาจากพื้นฐานทั้งสองโดนการใช้productกับsum
ด้วยความรู้ใหม่นี้เรามามองในมุมมองใหม่ของconstructorของtypeMaybe
data Maybe a = Nothing | Just aมันคือsumของtypeสองแบบและเราได้รู้ว่าsumนั้นมีความเป็นfunctorในส่วนแรกNothingสามารถที่จะถูกแสดงในรูปแบบของConst ()ที่กระทำบนa (parameterของtypeแรกของConstที่ถูกกำหนดให้เป็นunit หลังจากนี้เราจะเห็นการใช้Constที่น่าสนใจ) ในส่วนที่สองก็คือแค่ชื่อที่ต่างไปของidentity functor เราอาจจะนิยามMaybeจนถึงความisomorphismว่า
type Maybe a = Either (Const () a) (Identity a)ดังนั้นMaybeคือการประกอบกันของbifunctorEitherคู่กับสองfunctorอย่างConst ()และIdentity (Constนั้นจริงๆแล้วเป็นbifunctorแต่ในที่นี้เราได้ใช้มันแค่บางส่วนตลอดเวลา)
เราได้เห็นแล้วว่าfunctorที่ประกอบกันคือfunctor เราสามารถที่จะโน้มน้าวเราเองง่ายๆว่าbifunctorก็เป็นเช่นเดียวกัน ทั้งหมดที่เราต้องมีคือการหาวิธีที่bifunctorที่ถูกประกอบคู่กับfunctorสองตัวจะทำงานบนmorphism ถ้ามีmorphismอยู่สองตัวเราแค่liftตัวหนึ่งด้วยfunctorตัวหนึ่งและliftอีกตัวด้วยfunctorอีกตัวหนึ่ง เราจึงliftคู่ของmorphismที่ถูกliftที่เป็นผลมาจากก่อนหน้านี้ด้วยbifunctor
เราสามารถที่จะแสดงการประกอบกันในHaskell เรามานิยามtypeของdataที่ถูกparameterizedโดยbifunctorbf (มันคือตัวแปรแบบtypeที่ก็คือconstructorของtypeที่นำสองtypeมาในฐานะargument) functorทั้งสองอย่างfuและgu(constructorของtypeที่นำตัวแปรแบบtypeมาแต่ละอย่าง) และtypeทั่วๆไปaและb เราใช้fuไปกับaและguไปกับbแล้วก็ใช้bfกับผลลัพธ์ที่เป็นทั้งสองtype
newtype BiComp bf fu gu a b = BiComp (bf (fu a) (gu b))นั่้นคือการประกอบกันของวัตถุหรือtype สังเกตว่าในHaskellเราใช้constructorของtypeกับtypeต่างๆ เหมือนกับการที่เราใช้functionไปกับargumentต่างๆ ที่มีsyntaxเหมือนกัน
ถ้าคุณสับสนเล็กน้อยลองใข้BiCompไปยังEither,Const (),Identity,aและbในลำดับนี้ คุณจะได้อีกรูปที่พื้นฐานแบบหนึ่งของMaybe bกลับมา(aก็ถูกเมินเฉย)
typeข้อมูลอันใหม่BiCompคือbifunctorบนaและbแต่แค่bfนั้นคือBifunctorเองและfuและguคือFunctor complierต้องรู้ว่าได้มีนิยามของbimapอยู่สำหรับbfและนิยามของfmapในfuและgu ในHaskellนี่สามารถถูกแสดงในฐานะเงื่อนไขเบื้องต้นในการประกาศของinstance นั้นก็คือชุดของความต้องการของclass (class constraints)ตามด้วยลูกศรคู่
instance (Bifunctor bf, Functor fu, Functor gu) =>
Bifunctor (BiComp bf fu gu) where
bimap f1 f2 (BiComp x) = BiComp (bimap (fmap f1) (fmap f2) x)ในการเขียนของbimapสำหรับBiCompที่มาในรูปแบบของbimapสำหรับbfและfmapsทั้งสองสำหรับfuและgu complierนั้นอนุมานโดยอัตโนมัติสำหรับtypesทั้งหมดและเลือกfunctionที่ถูกoverloadได้อย่างถูกต้องในทุกๆตอนที่BiCompถูกใช้
xในนิยามของbimapนั้นมีtypeเป็นแบบนี้
bf (fu a) (gu b)ที่ที่ค่อนข้างมีขนาดใหญ่ bimapรอบนอกทะลุผ่านชั้นของbfและfmapทั้งสองที่อยู่ภายใต้fuและguตามลำดับ ถ้าtypeของf1และf2คือ
f1 :: a -> a'
f2 :: b -> b'แล้วผลลัพธ์สุดท้ายของtype bf (fu a') (gu b')คือ
bimap :: (fu a -> fu a') -> (gu b -> gu b')
-> bf (fu a) (gu b) -> bf (fu a') (gu b')ถ้าคุณชอบปัญหาจิ๊กซอว์ การโยกย้ายtypeแบบนี้สามารถให้ความบันเทิงกับคุณเป็นชั่วโมงเลย
ดังนั้นมันกลับเป็นว่าเราไม่ต้องที่จะพิสูจน์ว่าMaybeเป็นfunctor ความจริงนี้ตามมาจากวิธีการที่มันถูกสร้างในฐานะsumของพื้นฐานที่มีความเป็นfunctor
ผู้อ่านที่ช่างสังเกตอยากจะถามคำถามว่า ถ้าการคำนวณinstaceของFunctorสำหรับtypeข้อมูลแบบพีชคณิตนั้นมีความเป็นกลไกอย่างมาก แล้าเราสามารถทำให้การทำแบบนี้เป็นอัตโนมัติและกระทำโดยcomplierได้หรือเปล่า แน่นอนว่ามันสามารถทำได้และมันทำอยู่ คุณต้องเปิดใช้งานextensionของHaskellบางตัวโดยการนำบรรทัดนี้เข้ามาข้างบนของไฟล์ของโค้ด(source file)
{-# LANGUAGE DeriveFunctor #-}แล้วก็เพิ่มderiving Functorไปยังdata structureของคุณ
data Maybe a = Nothing | Just a deriving Functorแล้วfmapที่สอดคล้องกันก็จะถูกเขียนให้คุณ
ความเป็นระเบียบของdata strctureแบบพีชคณิตทำให้มันเป็นไปได้ที่จะสร้างinstanceที่ไม่ใช่แค่สำหรับFunctor แต่type classต่างๆอีกหลายตัวรวมไปถึงEqtype classที่ผมพูดถึงก่อนหน้านี้ มันได้มีทางเลือกในการสอนcomplierในการสร้างinstancesสำหรับtype classsของคุณแต่นั้นค่อนข้างขั้นสูงไปหน่อย แนวคิดจะเหมือนกันคือคุณให้พฤติกรรมสำหรับส่วนประกอบพื้นฐานและการsumและproductและให้complierคิดในส่วนที่เหลือ
9.4 FunctorในC++
ถ้าคุณเป็นคนที่เขียนC++แน่นอนว่าคุณนั้นอยู่ตัวคนเดียวสำหรับการเขียนfuntor แต่คุณควรที่สามารถที่จะมองเห็นtypeบางตัวของdata structureแบบพีชคณิตในC++ ถ้าdata structureแบบนั้นถูกสร้างให่้เป็นtemplateทั่วไป(generic template) คุณก็ควรที่จะสามารถเขียนfmapสำหรับมัน
เรามาดูที่data structureแบบtreeที่เราต้องการที่จะนิยามในHaskellในฐานะtypeแบบsumและrecursive
data Tree a = Leaf a | Node (Tree a) (Tree a)
deriving Functorเหมือนกับการที่ผมเอ่ยถึงก่อนหน้านี้ วิธีหนึ่งในการเขียนtypeแบบsumในC++ คือผ่านลำดับชั้นของclass มันอาจจะเป็นธรรมชาติในภาษาแบบobject-orientedในการเขียนfmapในฐานะfunctionแบบvirtualของclassพื้นฐานอย่างFunctorและก็overrideมันในsubclassทั้งหมด น่าเสียดายว่าสิ่งนี้เป็นไปไม่ได้เพราะfmapคือtemplate ที่parameterizedไม่ได้แค่โดยtypeของวัตถุที่มันกระทำต่อ (pointerของthis)แต่ก็รวมไปถึงtypeที่returnของfunctionที่ถูกนำมาใช้กับมัน functionแบบvirtualไม่สามารถที่จะทำให้เป็นtemplateในC++ได้ เราจะเขียนfmapในฐานะgeneric free function และเราจะแทนที่การจับคู่รูปแบบด้วยdynamic_cast
classฐานต้องนิยามfunctionแบบvirtualหนี่งตัวเป็นอย่างน้อยเพื่อที่จะสนับสนุนการcastingแบบdynamics ดังนั้นเราจะทำdestructorเป็นvirtual (ที่ก็เป็นแนวคิดที่ดีในทุกๆกรณี)
template<class T>
struct Tree {
virtual ~Tree() {}
};Leftก็เป็นแค่functorIdentityแบบแอบๆ
template<class T>
struct Leaf : public Tree<T> {
T _label;
Leaf(T l) : _label(l) {}
};Nodeเป็นtypeแบบproduct
template<class T>
struct Node : public Tree<T> {
Tree<T> * _left;
Tree<T> * _right;
Node(Tree<T> * l, Tree<T> * r) : _left(l), _right(r) {}
};ในการเขียนfmapเราได้ใช้การdispatchingแบบdynamicบนtypeของTreeให้เป็นประโยชน์ ในกรณีของLeafใช้รูปแบบIdentityของfmapและในกรณีของfmapก็ถูกปฏิบัติเหมือนbifunctorที่ถูกประกอบคู่กับTreefunctorสองตัว ในฐานะคนที่เขียนC++ คุณอาจจะไม่คุ้นเคยกับการวิเคราะห์โค้ดในแบบนี้แต่มันเป็นการฝึกที่ดีในการคิดแบบcategorical
template<class A, class B>
Tree<B> * fmap(std::function<B(A)> f, Tree<A> * t) {
Leaf<A> * pl = dynamic_cast <Leaf<A>*>(t);
if (pl)
return new Leaf<B>(f (pl->_label));
Node<A> * pn = dynamic_cast<Node<A>*>(t);
if (pn)
return new Node<B>( fmap<A>(f, pn->_left)
, fmap<A>(f, pn->_right));
return nullptr;
}เพิ่อความง่ายดาย ผมตัดสินใจที่จะไม่สนใจกับปัญหาของการจัดการmemoryและทรัพยากร แต่ในโด้ดที่ใช้ในproductionคุณอาจจะต้องใช้smart pointer(ที่เป็นเอกลักษณ์หรือใช้ร่วมกัน แล้วแต่นโยบายของคุณ)
นำมาเทียบกับการเขียนในHaskellของfmap
instance Functor Tree where
fmap f (Leaf a) = Leaf (f a)
fmap f (Node t t') = Node (fmap f t) (fmap f t')การเขียนนี้ก็สามารถถูกสร้างโดยcomplierเช่นกัน
9.5 Writer Functor
ผมสัญญาว่าผมจะกลับมาที่categortyแบบkleisliที่ผมอธิบายก่อนหน้านี้ morphismในcategoryนั้นถูกแสดงโดยfunctionที่ผ่านการประดับแล้วที่return data structureแบบWriter
type Writer a = (a, String)ผมได้พูดก่อนหน้านี้ว่าการประดับของfunctionนั้นมีความเกี่ยวข้องบางอย่างกับendofunctor และแน่นอนว่าconstructorของtypeอย่างWriterนั้นมีความเป็นfunctorในa เราไม่ต้องที่จะมีการเขียนของfmapสำหรับมันเพราะว่ามันก็เป็นแค่typeแบบproduct
แต่อะไรคือความสัมพันธ์ระหว่างcategoryแบบKleisliและfunctorโดยทั่วไปละ? ในการที่categoryแบบKleisliเป็นcategory มันนั้นได้นิยามการประกอบกันและidentity ให้ผมได้เตือนความจำคุณว่าการประกอบกันนั้นถูกให้โดยfish operator
(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)
m1 >=> m2 = \x ->
let (y, s1) = m1 x
(z, s2) = m2 y
in (z, s1 ++ s2)และmorphismแบบidentityถูกให้โดยfunctionที่ถูกเรียกว่าreturn
return :: a -> Writer a
return x = (x, "")มันกลายมาเป็นว่าถ้าคุณมองที่typeของfunctionทั้งสองมาพอ(และผมหมายถึงนานมากพอจริงๆ) คุณฏ้จะสามารถหาวิธีการในการรวมพวกมันเข้าเดียวกันในการสร้างfunctionที่มีtype signatureที่ถูกต้องเพื่อที่จะนำมาใช้ในฐานะfmapได้ดังต่อไปนี้
fmap f = id >=> (\x -> return (f x))ในที่นี้fish operatorได้รวมสองfunction หนึ่งในนั้นคือidที่คุ้นเคยและอีกตัวหนึ่งคือlambdaที่ใช้returnผลลัพธ์ของf ที่ทำบนargumentของlambnda ส่วนที่ยากที่สุดที่จะทำความเข้าใจก็คงเป็นการใช้id ไม่ไช่หรอที่argumentของfish operatorควรที่จะเป็นfunctionที่นำtypeแบบ”ธรรมดา”และreturn typeผ่านการประดับแล้ว? ก็ไม่ตลอก ไม่มีใครบอกว่าaในa -> Writer bต้องเป็นtypeแบบ”ธรรมดา” มันเป็นตัวแปรแบบtypeดังนั้นมันสามารถที่จะเป็นอะไรก็ได้ โดยเฉพาะที่มันสามารถที่จะเป็นtypeที่ผ่านการประดับแล้วอย่างWriter b
ดังนั้นidจะรับWriter aและแปลมันเป็นWriter a fish operatorจะทำการดึงค่าของaและส่งไปในฐานะxไปยังlambda ที่ในที่นี้คือfจะกลายมาเป็นb และกาreturnจะประดับมันให้ได้มันมาเป็นWriter b นำทั้งหมดเข้าด้วยกันเราก็จะได้functionที่นำWriter aเขามาและส่งกลับมาเป็นWriter bในที่สุด ซึ่งเป็นสิ่งที่fmapควรที่จะสร้าง
สังเกตได้ว่าargumentนี้มีความทั่วไปเป็นอย่างมาก คุณสามมารถที่จะแทนที่Writerกับconstructorของtypeแบบไหนก็ได้ ตราบเท่าที่มันรับรองfist operatorและreturnคุณสามารถนิยามfmapได้เหมือนกัน ดังนั้นการประดับในcategoryแบบKleisliจึงเป็นfunctorโดยตลอด (แต่ไม่ไช่ทุกfunctorที่จะก่อให้เกิดเป็นcategoryแบบKleisi)
คุณอาจจะสงสัยว่าถ้าfmapที่เราพึ่งนิยามนั้นเหมือนกับfmapที่complierอาจจะสร้างผ่านderiving Functorหรือเปล่า? น่าสนใจไม่น้อยที่มันเป็นแบบเดียวกัน นี่ก็เป็นเพราะวิธีการที่Haskellเขียนfunctionsแบบpolymorphic จะถูกเรียกว่าparametric polymorphism และมันเป็นที่มาของสิ่งที่เรียกว่า ทฤษฎีบทที่ได้มาแบบฟรีๆ(theorems for free) หนึ่งในทฤษฎีบทเหล่านี้พูดว่า ถ้าได้มีการเขียนของfmapที่เก็บรักษาidentityไว้สำหรับconstructorของtypeที่ให้มา แล้วนั้น ก็จะมีการเขียนเพียงแบบเดียว
9.6 FunctorแบบCovariantและContravariant
ในตอนนี้เราได้พิจารณาWriter Functorเรามากลับมาที่Reader Functor มันมาจากconstructorของtypeแบบลูกศรfunctionที่ถูกใช้บางส่วน
(->) rเราสามารถที่จะเขียนใหม่ในtypeที่มีความหมายเดียวกัน
type Reader r a = r -> aที่instanceFunctorในที่ที่เราเห็นมาก่อนเขียนว่า
instance Functor (Reader r) where
fmap f g = f . gแต่ก็เหมือนกับcostructorของtype pairหรือconstructorของtypeEither constructorของtype functionนั้นนำargumentของtypeทั้งสองเข้ามา pairและEitherมีความเป็นfunctorในargumentทั้งสอง มันคือbifunctor แล้วconstructorของfunctionเป็นbifunctorด้วยหรือเปล่า?
เรามาลองที่จะทำมันให้มีความเป็นfunctorในargumentแรก เริ่มด้วยtypeที่มีความหมายเดียวกันมันแต่แค่Readerแต่ถูกสลับargument
type Op r a = a -> rในตอนนี้เรายึดtypeที่returnrไว้แล้วเปลี่ยนtypeของargumentaไปมา เรามาดูว่าเราสามารถที่จะให้typeต่างๆนั้นลงตัว เพื่อที่จะสามารถเขียนfmapที่ควรจะเป็นไปตามsignatureของtypeดังต่อไปนี้
fmap :: (a -> b) -> (a -> r) -> (b -> r)โดยมีfunctionสองตัวที่นำaมาแล้วก็returnbและrกลับมาตามลำดับ แต่มันไม่มีวิธีไหนในการสร้างfunctionที่นำbเข้ามาและreturnrกลับมา แต่ผลอาจจะแตกต่างถ้าเราสามารถที่จะสลับ(invert)functionตัวแรกเพื่อที่ว่ามันนำbเข้ามาและreturnaกลับมาแทน เราไม่สามารถสลับfunctionตามใจได้แต่เราสามารถไปยังcategoryตรงข้าม
สรุปอย่างคร่าวๆ สำหรับทุกๆcategory\(\textbf{C}\)ได้มีdual categoryอย่าง\(\textbf{C}^\text{op}\) ที่คือcategoryที่มีวัตถุเหมือนกับ\(\textbf{C}\)แต่ในทุกๆลูกศรอยู่ในทางตรงข้าม
ลองพิจารณาfunctorระหว่าง\(\textbf{C}^\text{op}\)และอีกcategory\(\textbf{D}\)ตัวหนึ่ง
\[ F::\textbf{C}^\text{op}\rightarrow\textbf{D} \]
functorแบบนี้โยงmorphism\(f^\text{op}::a\rightarrow b\)ใน\(\textbf{C}^\text{op}\) ไปยังmorphism\(f^\text{op}::Fa\rightarrow Fb\)ใน\(\textbf{D}\) แต่morphism\(f^\text{op}\)นั้นคู่กับmorphism\(f::b\rightarrow a\)อย่างลับๆในcategoryดังเดิม\(\textbf{C}\) โปรดสังเกตการกลับทาง
ในตอนนี้\(F\)เป็นfunctorธรรมดาแต่ได้มีการโยงที่เรานิยามโดยมีฐานมาจาก\(F\)ที่ไม่ใช่functor เรามาเรียกมันว่า\(G\)ที่โยงจาก\(\textbf{C}\)ไปยัง\(\textbf{D}\) มันโยงวัตถุในแบบเดียวกันกับ\(F\) แต่ในตอนที่มันโยงmorphismมันจะทำการกลับทางพวกมัน มันนำmorphism\(f::b\rightarrow b\)ใน\(\textbf{C}\)โยงไปเป็นmorphismตรงข้าม\(f^\text{op}::a\rightarrow b\) แล้วก็ใช้functor\(F\)กับมันเพื่อที่จะได้\(Ff^\text{op}:Fa\rightarrow Fb\)
ถ้าเราพิจารณาว่า\(Fa\)นั้นเหมือนกับ\(Ga\)และ\(Fb\)เหมือนกับ\(Gb\) ทั้งหมดสามารถที่จะถูกอธิบายอย่าง \(Gf::(b\rightarrow a)\rightarrow(Ga\rightarrow Gb)\) มันคือ”functorที่มีการแปลงเล็กน้อย” การโยงระหว่างcategoryต่างๆท่มีการกลับทิศทางของmorphismแบบนี้ จะถูกเรียกว่าfunctorแบบcontravariant สังเกตว่าfunctorแบบcontravariantนั้นก็เป็นแค่functorธรรมดาจากcategoryตรงข้าม อนึ่งfunctorธรรมดา(เป็นแบบที่เราได้ทำการศึกษาจนถึงจุดนี้) จะถูกเรียกว่าfunctorแบบcovariant
ในที่นี้typeclassที่นิยามfunctorแบบcontravariant (จริงๆก็คือendofunctorแบบcontravariant) ในHaskellที่ก็คือ
class Contravariant f where
contramap :: (b -> a) -> (f a -> f b)construnctorของtypeOpคือinstanceของมัน
instance Contravariant (Op r) where
-- (b -> a) -> Op r a -> Op r b
contramap f g = g . fสังเกตว่าfunctionfใส่ตัวเองเข้าก่อน(นั่นก็คืออยู่ทางด้านขวาของ) เนื้อหาของOp นั้นก็คือfunctiong
นิยามของcontramapสำหรับOp สามารถทำให้กระชับมากขึ้นถ้าคุณสังเกตว่ามันคือแค่operatorในการประกอบfunctionที่argumentถูกสลับ ได้มีfunctionพิเศษสำหรับการสลับargument เรียกว่าflip
flip :: (a -> b -> c) -> (b -> a -> c)
flip f y x = f x yในแบบนี้เราก็จะได้
contramap = flip (.)9.7 Profunctors
เราได้เห็นมาแล้วว่าoperatorของลูกศรfunctionนั้นเป็นแบบcontravariantในargumentตัวแรก และเป็นแบบcovariantในในargumentตัวที่สอง ได้มีชื่อสำหรับสิ่ง(ที่ดูน่ากลัวนี้)นี้หรือเปล่า? กลับเป็นว่าถ้าcategoryปลายทางเป็น\(\textbf{Set}\)แล้วสิ่งที่ดูน่ากลัวนี้จะถูกเรียกว่าprofunctor เพราะว่าfunctorแบบcontravariantนั้นเท่ากับfunctorแบบcovariantจากcategoryตรงข้าม profunctorนั้นจะถูกนิยามว่า
\[ \textbf{C}^\text{op}\times\textbf{D}\rightarrow\textbf{Set} \]
เนื่องว่าในการประมาณคร่าวๆว่าtypeของHaskellคือset เราได้ใช้ชื่อของProfunctorไปยังconstructorสองargumentของtypep ที่มีความเป็นcontra-functorในargumentแรกและความเป็นfunctorในargumentที่สอง นี่คือtypeclassที่ถูกต้องที่มาจากlibraryData.Profunctorอย่าง
class Profunctor p where
dimap :: (a -> b) -> (c -> d) -> p b c -> p a d
dimap f g = lmap f . rmap g
lmap :: (a -> b) -> p b c -> p a c
lmap f = dimap f id
rmap :: (b -> c) -> p a b -> p a c
rmap = dimap idfunctionทั้งสามมาคู่กับค่าเริ่มต้น เหมือนกับBifunctorในการประกาศinstanceของProfunctor คุณต้องมีทางเลือกของการเขียนdimapและทำการยอมรับค่าเริ่มต้นสำหรับlmapและrmap หรือเขียนทั้งlmapและrmapและยอมรับค่าเริ่มต้นสำหรับdimap
ในตอนนี้เราสามารถยืนยันว่าoperatorแบบลูกศรfunctionคือinstanceของProfunctor
instance Profunctor (->) where
dimap ab cd bc = cd . bc . ab
lmap = flip (.)
rmap = (.)Profunctorถูกใช้ในlibaryของlensในHaskell เราจะเห็นพวกมันในตอนที่เราพูดเกี่ยวกับendsและcoends
9.8 FunctorของHom
ในตัวอย่างข้างบนคือภาพสะท้อนของstatementที่ว่าการโยง ที่นำคู่ของวัตถุ\(a\)และ\(b\)และกำหนดsetของmorphismระหว่างมัน(hom-set\(\textbf{C}(a,b)\)) คือfunctor มันคือfunctorจากcategoryแบบproduct\(\textbf{C}^\text{op}\times\textbf{C}\)ไปยังcategoryของsetอย่าง\(\textbf{Set}\)
เรามานิยามการกระทำของมันบนmorphism morphismใน\(\textbf{C}^\text{op}\times\textbf{C}\) คือคู่ของmorphismจาก\(\textbf{C}\)
\[ \begin{gather*} f :: a' \to a \\ g :: b \to b' \end{gather*} \]
การliftของคู่นี้ต้องเป็นmorphism(function)จากset \(\textbf{C}(a,b)\)ไปยัง\(\textbf{C}(a',b')\) เราแค่ต้องเลือกสมาชิก\(h\)ของ\(\textbf{C}(a,b)\) (มันคือmorphismจาก\(a\)ไปยัง\(b\)) และกำหนดมันไปยัง
\[ g\circ h\circ f \]
ที่ก็คือสมาชิกของ\(\textbf{C}(a',b')\)
คุณได้เห็นแล้วว่าhom-functorเป็นกรณีพิเศษของprofunctor
9.9 โจทย์ท้าทาย
- ลองแสดงดูว่าtypeของข้อมูล
data Pair a b = Pair a bคือbifunctor สำหรับคะแนนเพิ่มให้ลองเขียนทั้งสามmethod ของBifunctorและใช้การให้เหตุผลทางสมการ ในการแสดงว่าการนิยามพวกนี้นั้นเข้ากันได้กลับค่าเริ่มต้นในทุกๆตอนที่มันถูกใช้
- ลองแสดงisomorphismระหว่างนิยามมาตรฐานของ
Maybeและนิยามที่ตรงไปตรงมาอย่าง(desugaring)
type Maybe' a = Either (Const () a) (Identity a)คำใบ้:นิยามการโยงสองตัวระหว่างการเขียนทั้งสอง สำหรับคะแนนเพิ่มลองแสดงว่าพวกมันคือinverseระหว่างกันโดยการใช้เหตุผลทางสมการ
- เรามาลองdata structureอีกอัน เราเรียกมันว่า
PreListเพราะว่ามันคือจุดเริ่มของListมันแทนที่recursionด้วยparameterแบบtypeb
data PreList a b = Nil | Cons a bเราอาจจะกู้นิยามก่อนหน้านี้ของListโดยการใช้งานPreListไปกับตัวเอง (เราจะเห็นวิธีการในการทำมันในตอนที่เราพูดเกี่ยวกับfixed points) และลองแสดงว่าPreListคือinstanceของBifunctor
- แสดงว่าtypeแบบข้อมูลนิยามbifunctorใน
aและb
data K2 c a b = K2 c
data Fst a b = Fst a
data Snd a b = Snd bสำหรับคะแนนเพิ่มลองตรวจสอบคำตอบของคุณกับpaperของConor McBrideอย่างClowns to the Left of me, Jokers to the Right(ตัวตลกอยู่ด้านช้าย โจ๊กเกอร์อยู่ด้านชวา)1
นิยามbifunctorในภาษาที่มีมากกว่าHaskell ลองเขียน
bimapสำหรับpairแบบทั่วไปในภาษานั้นstd::mapควรที่จะถูกพิจารณาเป็นbifunctorหรือprofunctor ในargumentของtemplateKeyและT? แล้วคุณจะทำการออกแบบtypeแบบข้อมูลใหม่ที่จะทำให้เป็นแบบนั้นหรือเปล่า?