ในการเขียนโปรแกรมคอมพิวเตอร์ อนามอร์ฟิซึม (anamorphism)คือฟังก์ชันที่สร้างลำดับโดยการประยุกต์ใช้ฟังก์ชันนั้นซ้ำๆ กับผลลัพธ์ก่อนหน้า คุณเริ่มต้นด้วยค่า A และใช้ฟังก์ชัน f กับค่า A เพื่อให้ได้ค่า B จากนั้นคุณใช้ f กับ B เพื่อให้ได้ค่า C และทำเช่นนี้ต่อไปเรื่อยๆ จนกว่าจะถึงเงื่อนไขสิ้นสุด ฟังก์ชันอนามอร์ฟิซึมคือฟังก์ชันที่สร้างลำดับของ A, B, C เป็นต้น คุณสามารถคิดว่าอนามอร์ฟิซึมเป็นการคลี่ค่าเริ่มต้นออกเป็นลำดับ

คำอธิบายแบบง่ายๆ ข้างต้นสามารถกล่าวได้อย่างเป็นทางการมากขึ้นในทฤษฎีหมวดหมู่ : อนามอร์ฟิซึมของประเภทโคอินดักที ฟ หมายถึงการกำหนดโคอัลจีบรา ให้กับ มอร์ฟิซึมเฉพาะของมันไปยังโคอัลจีบราสุดท้ายของเอนโดฟังก์ชันเตอร์วัตถุเหล่านี้ใช้ในการเขียนโปรแกรมเชิงฟังก์ชันในรูปแบบของการคลี่ออก

ฟังก์ชันคู่เชิงหมวดหมู่ (ฟังก์ชันที่ถือว่าเป็น "สิ่งที่ตรงกันข้าม" มากที่สุด) ของอนามอร์ฟิซึมคือคา ตามอร์ฟิซึม

ในการเขียนโปรแกรมเชิงฟังก์ชันอนามอร์ฟิซึมเป็นการขยายแนวคิดของการคลี่คลายบนลิสต์ แบบเหนี่ยวนำร่วม (coinductive lists) ใน ทางทฤษฎี อนามอร์ฟิซึมคือฟังก์ชันทั่วไปที่สามารถสร้างผลลัพธ์ของประเภท ใดประเภทหนึ่ง ได้แบบเรียกซ้ำ ร่วม (corecursively ) และมีพารามิเตอร์เป็นฟังก์ชันที่กำหนดขั้นตอนถัดไปของการสร้าง

ชนิดข้อมูลที่กล่าวถึงนี้ถูกนิยามว่าเป็นจุดตรึงที่ใหญ่ที่สุดν X . FXของฟังก์ชันFโดยคุณสมบัติสากลของคอลเจบราสุดท้าย จะมีมอร์ฟิซึมคอลเจบราA → ν X . FX ที่ไม่ซ้ำกันสำหรับ คอลเจบราFอื่นๆa : A → FAดังนั้น เราสามารถกำหนดฟังก์ชันจากชนิดAไปยังชนิดข้อมูลแบบเหนี่ยวนำร่วมได้โดยการระบุโครงสร้างคอลเจบรา aบนA

ตัวอย่างเช่น ประเภทของลิสต์ ที่อาจไม่มีที่สิ้นสุด (โดยมีองค์ประกอบที่มีค่า ประเภทคงที่ ) จะถูกกำหนดเป็นจุดคงที่[value] = ν X . value × X + 1กล่าวคือ ลิสต์ประกอบด้วยค่าหนึ่งและลิสต์อื่น หรืออาจเป็นลิสต์ว่างเปล่า นิยาม (แบบจำลอง) ของ Haskellอาจมีลักษณะดังนี้:

ข้อมูล[ ค่า] = ( ค่า: [ ค่า]) | []

เป็นจุดคงที่ของฟังก์ชันF valueโดยที่:

ข้อมูลMaybe a = Just a | Nothing ข้อมูลF value x = Maybe ( value , x )

เราสามารถตรวจสอบได้อย่างง่ายดายว่าชนิดข้อมูลนั้น[value]เป็นไอโซมอร์ฟิกกับ F value [value]และดังนั้น จึง[value]เป็นจุดตรึง (โปรดทราบด้วยว่าใน Haskell จุดตรึงที่เล็กที่สุดและใหญ่ที่สุดของฟังก์ชันจะตรงกัน ดังนั้นรายการอุปนัยจึงเหมือนกับรายการโคอินดักทีฟซึ่งอาจเป็นอนันต์)

อนามอร์ฟิซึมสำหรับลิสต์ (ซึ่งในสมัยนั้นมักเรียกว่าunfold ) จะสร้างลิสต์ (ซึ่งอาจเป็นอนันต์) จากค่าสถานะ โดยทั่วไป unfold จะรับค่าสถานะxและฟังก์ชันfที่ส่งคืนค่าคู่หนึ่งกับสถานะใหม่ หรือค่าเดียวเพื่อระบุจุดสิ้นสุดของลิสต์ จากนั้นอนามอร์ฟิซึมจะเริ่มต้นด้วยค่าเริ่มต้นแรก คำนวณว่าลิสต์ยังคงดำเนินต่อไปหรือสิ้นสุด และในกรณีที่ลิสต์ไม่ว่างเปล่า จะเพิ่มค่าที่คำนวณได้ไว้ข้างหน้าการเรียกซ้ำของอนามอร์ฟิซึม

นิยามของฟังก์ชัน unfold หรือ anamorphism สำหรับลิสต์ในภาษา Haskell ซึ่งเรียกว่าana`unfold` มีดังนี้:

ana :: ( state -> Maybe ( value , state )) -> state -> [ value ] ana f stateOld = case f stateOld of Nothing -> [] Just ( value , stateNew ) -> value : ana f stateNew

ตอนนี้เราสามารถใช้งานฟังก์ชันทั่วไปต่างๆ โดยใช้ana ได้ แล้ว ตัวอย่างเช่น การนับถอยหลัง:

f :: Int -> Maybe ( Int , Int ) f current = let oneSmaller = current - 1 in if oneSmaller < 0 then Nothing else Just ( oneSmaller , oneSmaller )

ฟังก์ชันนี้จะลดค่าจำนวนเต็มลงทีละหนึ่งและแสดงผลลัพธ์ไปพร้อมกัน จนกว่าค่าจะเป็นลบ ซึ่งเมื่อถึงจุดนั้นจะถือเป็นจุดสิ้นสุดของรายการ ในทำนองเดียวกัน ฟังก์ชันนี้ จะ คำนวณ ana f 3รายการ[2,1,0]

สามารถกำหนดรูปแบบอนามอร์ฟิซึมสำหรับประเภทเรียกซ้ำใดๆ ก็ได้ โดยอิงตามรูปแบบทั่วไป ซึ่งเป็นการขยายรูปแบบอนามอร์ฟิ ซึมเวอร์ชันที่สอง สำหรับลิสต์

ตัวอย่างเช่น การคลี่โครงสร้างข้อมูลแบบต้นไม้

ข้อมูลTree a = Leaf a | Branch ( Tree a ) a ( Tree a )

มีรายละเอียดดังต่อไปนี้

ana :: ( b -> Either a ( b , a , b )) -> b -> Tree a ana unspool x = case unspool x of Left a -> Leaf a Right ( l , x , r ) -> Branch ( ana unspool l ) x ( ana unspool r )

เพื่อให้เห็นความสัมพันธ์ระหว่างประเภทแบบเรียกซ้ำและการแปลงแบบอนามอร์ฟิซึมได้ดียิ่งขึ้น โปรดสังเกตว่าTreeและListสามารถกำหนดได้ดังนี้:

สร้าง List a ใหม่โดยใช้List ที่มี ชื่อเดียวกัน คือunCons :: Maybe ( a , List a )newtype Tree a = Tree { unNode :: Either a ( Tree a , a , Tree a ))}

ความคล้ายคลึงกับanaที่ปรากฏโดยการเปลี่ยนชื่อbในประเภท:

newtype List a = List { unCons :: Maybe ( a , List a )} anaList :: ( list_a -> Maybe ( a , list_a )) -> ( list_a -> List a )newtype Tree a = Tree { unNode :: Either a ( Tree a , a , Tree a ))} anaTree :: ( tree_a -> Either a ( tree_a , a , tree_a )) -> ( tree_a -> Tree a )

ด้วยคำจำกัดความเหล่านี้ อาร์กิวเมนต์ของคอนสตรัคเตอร์ของประเภทจะมีประเภทเดียวกับประเภทการส่งคืนของอาร์กิวเมนต์แรกของanaโดยที่การกล่าวถึงประเภทแบบเรียกซ้ำจะถูกแทนที่bด้วย

หนึ่งในสิ่งพิมพ์แรกๆ ที่แนะนำแนวคิดของอนามอร์ฟิซึมในบริบทของการเขียนโปรแกรมคือบทความFunctional Programming with Bananas, Lenses, Envelopes and Barbed Wire [ ^{1 ] โดย} Erik Meijer และคณะซึ่งอยู่ในบริบทของภาษาการเขียนโปรแกรม Squiggol

ฟังก์ชันอย่าง ` zipand` iterateเป็นตัวอย่างของอนามอร์ฟิซึม ` zipand` รับคู่ของลิสต์ เช่น `['a','b','c']` และ `[1,2,3]` และส่งคืนลิสต์ของคู่ `[('a',1),('b',2),('c',3)]` ส่วน ` Iterateor` รับสิ่งของ `x` และฟังก์ชัน `f` จากสิ่งของดังกล่าวไปยังสิ่งของดังกล่าว และส่งคืนลิสต์อนันต์ที่ได้จากการประยุกต์ใช้ฟังก์ชัน `f` ซ้ำๆ นั่นคือลิสต์ `[x, (fx), (f (fx)), (f (f (fx))), ...]`

zip ( a : as ) ( b : bs ) = if ( as == [] ) || ( bs == [] ) -- || หมายถึง 'หรือ' แล้ว[( a , b )] มิฉะนั้น( a , b ) : ( zip as bs ) iterate f x = x : ( iterate f ( f x ))

เพื่อพิสูจน์สิ่งนี้ เราสามารถนำทั้งสองอย่างมาใช้ได้โดยใช้ฟังก์ชัน unfold ทั่วไปของเราanaโดยใช้รูทีนแบบเรียกซ้ำอย่างง่าย:

zip2 = ana unsp fin where fin ( as , bs ) = ( as == [] ) || ( bs == [] ) unsp (( a : as ), ( b : bs )) = (( a , b ),( as , bs ))iterate2 f = ana ( \ a -> ( a , f a )) ( \ x -> False )

ในภาษาอย่าง Haskell แม้แต่ฟังก์ชันนามธรรมfold, unfoldและanaก็เป็นเพียงคำที่ถูกกำหนดขึ้นเท่านั้น ดังที่เราได้เห็นจากคำจำกัดความที่กล่าวมาข้างต้น

ในทฤษฎีหมวดหมู่อนามอร์ฟิซึมคือคู่เชิงหมวดหมู่ของคาตามอร์ฟิซึม (และคาตามอร์ฟิซึมคือคู่เชิงหมวดหมู่ของอนามอร์ฟิซึม)

นั่นหมายความว่าดังต่อไปนี้ สมมติว่า ( A , fin ) เป็นF -coalgebra สุดท้าย สำหรับendofunctor F บางตัว ของหมวดหมู่ บางหมวด หมู่ในตัวมันเอง ดังนั้นfinเป็นมอร์ฟิซึมจากAไปยังFAและเนื่องจากถือว่ามันเป็นสุดท้าย เราจึงรู้ว่าเมื่อใดก็ตามที่ ( X , f ) เป็นF -coalgebra อีกตัวหนึ่ง (มอร์ฟิซึมfจากXไปยังFX ) จะมีโฮโมมอร์ฟิซึมhที่ ไม่ซ้ำกัน จาก ( X , f ) ไปยัง ( A , fin ) นั่นคือมอร์ฟิซึมhจากXไปยังAโดยที่fin.h = Fh.f จากนั้นสำหรับแต่ละf ดัง กล่าวเราจะใช้สัญลักษณ์ana f แทนมอร์ฟิซึม hที่ระบุอย่างไม่ซ้ำกัน

กล่าวอีกนัยหนึ่ง เรามีความสัมพันธ์เชิงนิยามดังต่อไปนี้ โดยกำหนดค่าF , Aและfin ไว้คงที่ ดังที่กล่าวมาข้างต้น:

• ${\displaystyle h=\mathrm {ana} \ f}$
• ${\displaystyle \mathrm {fin} \circ h=Fh\circ f}$

สัญลักษณ์ที่ใช้แทน anamorphism ที่พบในเอกสารคือวงเล็บที่ใช้เรียกว่าวงเล็บเลนส์ซึ่งบางครั้งจึงเรียก anamorphism ว่าเลนส์ ตามวงเล็บนี้ ${\displaystyle [\!(f)\!]}$

• สัณฐานวิทยา
• มอร์ฟิซึมของพีชคณิต F
  • จากพีชคณิตเบื้องต้นไปสู่พีชคณิต: คาตาโมฟิซึม
  • อนามอร์ฟิซึมตามด้วยแคตามอร์ฟิซึม: ไฮโลมอร์ฟิซึม
  • การขยายแนวคิดเรื่องแคตามอร์ฟิซึม: พารามอร์ฟิซึม
  • การขยายแนวคิดเรื่องอนามอร์ฟิซึม: อะโพมอร์ฟิซึม

• อนามอร์ฟิซึมในฮัสเคลล์