## Saturday, December 4, 2010

### Type-level Fix and generic folds

This article describes a fixpoint combinator for Haskell types, with some justification of why such a thing would be useful. It's meant to be an accessible introduction to material which is already covered elsewhere.

You'll need some basic Haskell knowledge, such as how to define and use polymorphic data types. And you might want to first study the value-level `fix` function. An excellent introduction can be found here.

This code is standard Haskell 98, except in the "GHC tricks" section.

# Recursive types

Many useful data types are recursive:

``data Natural = Zero | Succ Natural     -- natural numbersdata List a  = Nil  | Cons a (List a)  -- listsdata Tree a  = Node a [Tree a]         -- rose trees``

In each case, the type declared on the left-hand side of "`=`" is mentioned on the right-hand side. This is fine, but just for fun let's see if there's another way.

We can imagine a language with a keyword "`self`", which refers to the type being defined:

``data Natural = Zero | Succ selfdata List a  = Nil  | Cons a selfdata Tree a  = Node a [self]``

Haskell doesn't have this keyword, so we'll make `self` into a type parameter:

``data NaturalF self = Zero | Succ selfdata ListF a  self = Nil  | Cons a selfdata TreeF a  self = Node a [self]``

We've changed the names because these aren't the types we wanted. They're non-recursive and each has an extra parameter.

To build the recursive type `Natural` using the non-recursive `NaturalF`, we need to "tie the knot":

``type Natural = NaturalF (NaturalF (NaturalF (NaturalF ...)))``

i.e.

``type Natural = NaturalF Natural``

But this is disallowed:

``````foo.hs:3:0:
Cycle in type synonym declarations:
foo.hs:3:0-30: type Natural = NaturalF Natural
``````

Since `type` defines a transparent synonym, this would generate an infinitely-large type-expression. Haskell disallows those. We need to hide the recursion behind a data constructor:

``newtype Natural = MkNat (NaturalF Natural)``

When we use this type, the "wrapper" constructor `MkNat` alternates with the constructors of `NaturalF`:

``toNatural :: Integer -> NaturaltoNatural 0 = MkNat ZerotoNatural n = MkNat . Succ \$ toNatural (n-1)``

# Type-level `Fix`

So far this is just pointless complexity. We've replaced one type:

``data Natural = Zero | Succ Natural``

with two types:

``data    NaturalF self = Zero | Succ selfnewtype Natural       = MkNat (NaturalF Natural)``

Notice that the definition of `Natural` doesn't depend on the structure of natural numbers. Let's rename `Natural` to `Fix` and `MkNat` to `In`:

``newtype Fix   = In (NaturalF Fix)``

Then we'll abstract out `NaturalF` as a type parameter `f`:

``newtype Fix f = In (f (Fix f))``

Now `Natural` is just a synonym:

``type Natural = Fix NaturalF``

When we create values of type `Natural`, we still have "wrapper" constructors:

``toNatural :: Integer -> NaturaltoNatural 0 = In ZerotoNatural n = In . Succ \$ toNatural (n-1)``

# Properties of `Fix`

Recall that the value-level `fix` function can be defined as

``fix f = f (fix f)``

This looks a lot like our type

``newtype Fix f = In (f (Fix f))``

The similarity is reflected at the type and kind levels:

``````GHCi> :t fix
fix :: (a -> a) -> a
GHCi> :k Fix
Fix :: (* -> *) -> *
``````

`fix` is a function which takes another function. `Fix` is a type constructor which takes another type constructor.

The types `Fix f` and `f (Fix f)` are isomorphic, and we'll want to convert between them. In one direction we'll use the data constructor

``In :: f (Fix f) -> Fix f``

and the other direction is easily defined as

``out :: Fix f -> f (Fix f)out (In x) = x``

# Folding lists

So why bother writing types this way? Well, we usually don't. But factoring the recursion out of our data type enables us to factor the recursion out of our functions.

Consider taking the sum of a list:

``sumF :: (Num a) => List a -> asumF (In Nil)         = 0sumF (In (Cons x xs)) = x + sumF xs``

We traverse the structure with the combining function `(+)`, making a recursive call at each recursive position of the data type. How can we capture this pattern?

If we're reducing a value of type `List T` to get a result of type `R`, then a value of type `ListF T R` represents a list node with the recursive call's result already in place. So we might look for a function like

``cata :: (ListF a b -> b) -> List a -> b``

If we had this, we could write

``sumF :: (Num a) => List a -> asumF = cata f where  f Nil = 0  f (Cons x xs) = x + xs``

The function `f` specifies one step of reduction, and the magical function `cata` handles the rest.

The recursion pattern captured by `cata` is very similar to `foldr` on the built-in list type. In fact, we can implement `foldr` with `cata`:

``foldrF :: (a -> b -> b) -> b -> List a -> bfoldrF f z = cata g where  g Nil = z  g (Cons x xs) = f x xs``

If `foldr` is good enough, then what's so special about `cata`? The answer is that `cata` actually has this very general type:

``cata :: (Functor f) => (f a -> a) -> Fix f -> a``

I'll give the one-line definition of `cata` later. Writing it yourself is a fun puzzle.

We can see that we'll need this instance:

``instance Functor (ListF a) where  fmap _ Nil         = Nil  fmap f (Cons x xs) = Cons x (f xs)``

This `fmap` just takes a function and applies it to the `self`-typed field, if any. It's not recursive and has no relation to the `[]` instance of `Functor`, for which `fmap = map`.

# Folding natural numbers

Let's put our generic `cata` to good use on another type. Every natural number is either zero, or the successor of another natural number:

``data NaturalF self = Zero | Succ selftype Natural = Fix NaturalF``

Again, `fmap` applies a function to each `self`-typed field:

``instance Functor NaturalF where  fmap _ Zero     = Zero  fmap f (Succ v) = Succ (f v)``

We can then use `cata` to define conversion to `Integer`:

``fromNatural :: Natural -> IntegerfromNatural = cata f where  f Zero     = 0  f (Succ n) = 1 + n``

as well as addition and multiplication:

``add :: Natural -> Natural -> Naturaladd n = cata f where  f Zero     = n  f (Succ m) = In \$ Succ mmul :: Natural -> Natural -> Naturalmul n = cata f where  f Zero     = In Zero  f (Succ m) = add n m``

Testing it:

``````GHCi> fromNatural (add (toNatural 2) (mul (toNatural 3) (toNatural 5)))
17

``````

# Folding rose trees

Let's try one more structure, namely rose trees:

``data TreeF a self = Node a [self]type Tree  a      = Fix (TreeF a)instance Functor (TreeF a) where  fmap f (Node v xs) = Node v (map f xs)``

As before, `fmap` applies a function to each `self`-typed field. Since we have a list of these, we use `map`.

We define some traversals:

``valuesF :: Tree a -> [a]valuesF = cata (\(Node x xs) -> x : concat xs)depthF :: Tree a -> IntegerdepthF = cata (\(Node _ xs) -> 1 + maximum (0:xs))``

and test them:

``````GHCi> let n x = In . Node x
GHCi> let t1 = n 'a' []
GHCi> valuesF t1
"a"
GHCi> depthF t1
1
GHCi> let t2 = n 'a' [n 'b' [], n 'c' [n 'd' []], n 'e' []]
GHCi> valuesF t2
"abcde"
GHCi> depthF t2
3

``````

# The definition of `cata`

As promised:

``cata :: (Functor f) => (f a -> a) -> Fix f -> acata g = g . fmap (cata g) . out``

# Generic programming

We usually manipulate data because we care about its meaning. But some operations only depend on the data's structure. If we have some complex nested data value, we might want to pretty-print it, or serialize it with binary, or collect all the `String`s buried within. These are concepts which apply to any data type you like. Shouldn't our code be similarly adaptable?

This idea is called generic programming. Implementations in Haskell include syb, uniplate, multiplate, instant-generics, GHC's built-in support, and many other efforts.

Each of these libraries demands certain information about each data type, and in return provides some generic operations. In this view, our above development of `Fix` constitutes a really tiny generics library. We require

• that you write recursive types as `Fix F`, where `F` is non-recursive, and
• that you provide `instance Functor F`.

In return, you get the single generic operation `cata`, which reduces a recursive structure to a "summary" value, by replacing each constructor with an arbitrary computation.

Our toy generics library is simple, but it doesn't actually save much work. Using `Fix` adds noise to the code, and our `Functor` instances aren't much shorter than a custom fold function for each type. Conversely, our uses of `cata` aren't much simpler than explicit recursive traversals.

Practicality aside, I think it's cool to define folding "once and for all". I'm interested to learn (from you!) what else can be done with `Fix`'d data or similar techniques.

For a non-trivial generics library built around similar ideas, see multirec and the accompanying paper.

# Odds and ends

## Nomenclature

`Fix` is sometimes named `Mu`, because the Greek letter μ is used to represent least fixed points.

`cata` stands for catamorphism.

Some of this stuff shows up in "Evolution of a Haskell Programmer". They build a factorial function using not only catamorphisms but also zygomorphisms and paramorphisms. Tell your friends!

In TaPL there's a discussion of equirecursive versus isorecursive type systems. Haskell is in the latter category. `Fix f` is isomorphic to, but not equivalent to, `f (Fix f)`. The functions `In` and `out` provide the isomorphism. If we defined `Fix` using `data` instead of `newtype`, the isomorphism would fail because of the extra value `In ⊥`.

## Isomorphisms

`NaturalF` is isomorphic to `Maybe`:

``data NaturalF self = Zero    | Succ selfdata Maybe    a    = Nothing | Just a``

The `Functor` instances are also the same.

`NaturalF` is also isomorphic to `ListF ()`, ignoring undefined values.

## GHC tricks

While the above is standard Haskell, we can pull a few more tricks by using a couple of GHC extensions.

GHC could help us reduce boilerplate by deriving `Functor` instances.

With some GHC extensions, we can write `Show` for `Fix`:

``instance (Show (f (Fix f))) => Show (Fix f) where  showsPrec p (In x) = showParen (p >= 11) (showString "In " . showsPrec 11 x)``

Testing it:

``````GHCi> toNatural 3
In (Succ (In (Succ (In (Succ (In Zero))))))
``````

This requires `-XFlexibleContexts` `-XUndecidableInstances`. The latter is required because `f (Fix f)` is a syntactically larger type than `Fix f`, so GHC can't convince itself that instance resolution will definitely terminate. For well-behaved arguments to `Fix`, it works out. We'll have something like

``-- from aboveinstance (Show (f (Fix f)))       => Show (Fix f)-- from 'deriving (Show)' on NaturalFinstance (Show self)       => Show (NaturalF self)``

which instantiates to

``instance (Show (NaturalF (Fix NaturalF)))       => Show (Fix NaturalF)instance (Show (Fix NaturalF))       => Show (NaturalF (Fix NaturalF))``

and GHC is clever enough to resolve the mutual recursion.

Remarkably, GHC can derive this instance with `-XStandaloneDeriving`:

``deriving instance (Show (f (Fix f))) => Show (Fix f)``

That's how I got the precedence-correct code above, via `-ddump-deriv`.

1. As an aside: in a strict language the least and greatest fixed point actually diverge. (In fact in a language with subtyping, they can further divide up based on the variance of the base functor. For example:

https://github.com/scalaz/scalaz/blob/master/core/src/main/scala/scalaz/Recursion.scala

2. I think the idea originated from this paper "Functional Programming with Overloading and Higher-Order Polymorphism".

3. This comment has been removed by a blog administrator.

4. I just made a generic programming library around the exact same idea. Using the Foldable and Traversable type classes on top of Functor, you can do much more than just catamorphisms: http://hackage.haskell.org/package/fixplate

You can also make Show work in the Haskell98 setting with a minimal amount of extra boilerplate.

5. شركة بريق متخصصة فى النظافة العامة بجدة تنظيف شقق فلل مكاتب مساجد تنظيف بالبخار بجدة تنظيف مفروشات ستائر مجالس سجاد كنب غسيل الاسطح وتنظيف الخزانات الكشف عن تسريبات المياه رش المبيدات وقتل الحشرات بأفضل الاسعار وأعلى جودة
شركة تنظيف منازل بجدة
شركة غسيل منازل بجدة
شركة تنظيف منازل بالبخار بجدة
شركة ترتيب وتنظيف المنازل بجدة
مكتب تنظيف منازل بجدة
شركة رسمية لتنظيف المنازل بجدة
مؤسسة رسمية لتنظيف المنازل بجدة
مين جربت شركات تنظيف المنازل بجدة
كم أسعار شركات تنظيف المنازل بجدة
أسعار شركات تنظيف المنازل بجدة
شركة تنظيف منازل بجده
تنظيف البيوت بجدة
شركة تنظيف كنب بجدة
شركة تنظيف بخار بجدة
شركة تنظيف فلل بجدة
شركة تنظيف شقق بجدة
شركة نظافة في جدة
شركة نظافة بجدة
ارخص شركه تنظيف بجده
شركه تنظيف بالبخار بجدة
تنظيف المسابح والخزانات
شركة تنظيف مجالس بجدة
شركة تنظيف مفروشات بالبخار بجدة
تنظيف الاسطح والارضيات
رش المبيدات ومكافحة الحشرات
عزل الأسطح والخزانات
نظافة شقق المغتربين والمقيمين
تنظيف الاستراحات تنظيف الخيام

6. I will be looking forward to your next post. Thank you
jajahuayfun.blogspot

7. Thanks for sharing such an informative article.

8. WOW! I Love it...
and i thing thats good for you >>

MOVIE TRAILER หนุมาน นักรบมนตรา
Thank you!

9. Amazing post, its is very helpful!
QuickBooks Customer Service is offering several ways to resolve all Common QuickBooks Pro Errors and Troubleshooting. If you face any issues related to this and you are not able to resolve it. Don't panic just dial QuickBooks Customer Service Toll-Free Number and get instant help.

kingabdullahsjf.com
freshstarthorserescue.org

11. This comment has been removed by the author.

12. Your blog is filled with unique good articles! I was impressed how well you express your thoughts.

True Voter App | True Voter

13. State Council of Educational Research and Training of the Telangana provides textbooks for all the subjects. Telangana SCERT Books by downloading or viewing them from our site. Refer to State Council of Educational Research Telangana 4th Class Books Research and Training Study Material for Classes 1,2,3,4,5,6,7,8,9,10 They make it easy for you in your preparation and fetching more marks in the exam.

14. Assam Class 11 Textbook list is released in online mode. AHSEC Board Class 11 books, syllabus, question papers and study materials details are given below. Assam 11th Standard Assamese, Hindi, English, Mathematics, Physics, AHSEC HS Books Biology, Chemistry, Botany, Zoology, Political Science, Economics, Business Studies, Accountancy, and other subjects EBooks will be updates on the official website.

Malwarebytes Crack is the most wonderful Anti-malware software that shows its performance by its name. This software is made for all the malware like viruses, Trojans, worms, and pests, etc. Malewarebytes is the kind of anti-malware software that has the ability to remove all the malware from the user’s system. All the malware has a very bad impact on the performance of the system even they make the system rough and idle. The presence of spyware also damages the system. In fact, all the malware can harm the system and they also have a very bad impact on the Windows of the PC.

16. Advanced SystemCare Ultimate Crack Free
Advanced SystemCare Ultimate Crack is the best operating software that provides all one solution to the users. It gives fast speed to your computer, which ultimately saves your time from standard processing time. Which is required each to process the normal operations? While not only to speed up the there, it gives protection to the computer. From any kind of antivirus and malware. Therefore, it utmost protection to your personal computer from any threat, which may become through online use or any type of ransomware.

17. Apowersoft Video Converter Studio CrackFree
Apowersoft Video Converter Studio Crack is the most fantastic and tremendous software. That has the talent to edit the videos on a wonderful level. This software is the most amazing software. That can convert the videos according to your plans. It can provide a shape to your ideas. Because it has all the obligatory structures or tools. That is very indispensable for the conversion of videos.

18. EasyWorship Crack
EasyWorship License Key combines innovative machines, including writing, words, and video. And the program has full diligence. Reduce the need for third-party code. Take full control of images and text in all functions such as reflection, ghosting, and relief.
It is easy to use and works in comparison to other important portrayal tools. It is also much better than quality and is the use of shiny tools. These tools are effortless to work. And do not require complex about using the software.

19. iTools Crack
iTools Serial Key performs the same task as iTunes performs. However, it is very comfortable to use. Millions of users are using this application. Also, it can manage all the files on your devices. Also more you can manage your files by using this according to your desire.

20. SketchUp Pro Crack Free
Google SketchUp Pro Keygen: There’s a reason SketchUp is similar to handy and forgiving 3D modelling program: we have a leaning towards sacrifice usability for the sake of practicality. Begin by drawing lines and shapes. Stretch, copy, and paint to form something you prefer. If you wish to be productive inside a few hours, you’ve come back to the correct place.

21. FL Studio Reg Key
FL Studio Crack is the most state-of-the-art and unmatched music creation software. And also more for the generation of fabulous melody, it can work with all and any type of music. By overwhelming this tool you can easily and smoothly compose the music according to your longing. Moreover, you can also consume it for editing the music in a very innocent and fairway. You can generate different types of effects on your music.

22. Windows Movie Maker Crack
Windows Movie Maker Crack is the most superb tool of this era. This software is used for the creation of videos. Similarly, it has the ability to make and edit the videos and after the editing, Windows Movie Maker Keygen Keys also has the ability to publish them on Facebook, Youtube, and One Drive. Nowadays video editing is a very easy task. There are many applications to edit the videos but there is no application like this. There is no match for this app. This software is very marvelous in its work.

23. SOUND FORGE Pro Crack
SOUND FORGE Pro Serial Number are present in this app to edit the sound like a magnifying tool, envelope tool, edit tool, event tool, and pencil tool. All these tools are necessary for editing. These four tools perform their own function and their functions are different from each other. If one of them is used for clearance than the other will be used to blur something. So, we can say that it’s the amazing and best software to alternate the sound. The strategy of this software is such that the users can easily interrelate with the software.

24. EaseUS Todo PCTrans Crack
EaseUS Todo PCTrans Crack is a PC transfer file software. That is best for all those people. Which want to transfer their all files from older PC to new One. There is a complete range of protection from the hacking of date. That up to USB Stick. Whether any kind of any external hard drive or DVD. The easiest way to describe the feature of this software. EaseUS Todo PCTrans Torrent Download is being a more secure moving day truck. While for all kinds of data. Whether it includes photos, files, folders, and music.

25. Connection issues among printers and PC: Some printers experience association issues with the network. Conceivably there is an issue with the remote network. The printer isn't getting the force supply: This is the normal error that users generally gripe about. Epson printer in error message It can happen because of issues with power strings that are being used. The printer won't get the correct force supply if there is an issue with the interfacing links. Establishment issues on the printer programming: Sometimes for issues with the establishment interaction printer can quit replying. Ensure that you introduce the printer programming appropriately. Ruined printer drivers: Corrupt printer drivers may likewise cause the non-activity of your printers. Drivers got harmed when it isn't modern. Now and again, outsider applications and infection contaminations can Also bring about degenerate printer drivers.

26. Manipur HSLC Model Paper The Board of Secondary Education, Manipur BSEM is responsible for constantly directing board assessments for students in Class 10. The Manipur HSLC Latest Question Paper 2022 will be published on the Manipur state BSEM website, According to the Manipur Board Model Paper. Board tests will begin in 2022, according to the Manipur Board Model Paper. Manipur HSLC Model Paper 2022 Continue reading this page because we will provide you with all the pertinent information about Manipur HSLC Previous Paper 2022. Continue reading to learn everything you need to know about Manipur Board Exam Previous Paper.

27. When will I get married? Will it be an arranged marriage or a love marriage? These are some of the questions that usually come to mind when someone reaches to marriageable age. If you are able to get the answers to your questions, then you will lead a happy and prosperous married life. You know what! Marriage prediction by date of birth is one of the best tools of Vedic Astrology that can help you to get the answers to these questions. A pioneer astrologer like Dr. Vinay Bajrangi can help you in getting things done symmetrically. If you need any kind of help, then contact him. He can give you Marriage predictions based on Vedic Astrology.

28. สล็อตเว็บตรง Slot games. Let me tell you that at the moment Probably no one is familiar with online gambling games and, of course, nowadays. There is only one type of online gambling game. that can make a profit for online gamblers The highest possible is a slot game.

29. We would be very pleased if you could come to สล็อตแตกง่าย

30. สล็อตxo
Fantastic postings, Cheers!
help writing grad school essay inexpensive resume writing services
We are a gaggle of volunteers and starting
a brand new scheme in our community.
สล็อตxo
Fantastic postings, Cheers!
help writing grad school essay inexpensive resume writing services
We are a gaggle of volunteers and starting
a brand new scheme in our community.

31. สล็อต wallet
My partner and I stumbled over here coming from a different website and thought I may as well check things out.
I like what I see so i am just following you. Look forward
to looking over your web page yet again 1

32. A disconnected printer error can likewise disapprove of the printer in error state software or driver. This can differ contingent upon the utilization of your printer and whether or not you have introduced refreshes. The printer investigating apparatus works with a wide scope of printers, including Canon, Brother, Epson, HP, and many others.

33. Very informative Information. Thanks for giving this type of information.
If you are looking for a Coin Master Free Spin and Coin Links then it is the right place for you. At this place, you will get the customer service support and 24/7 helpline number of Coin Master Free Spin for this you just have to click on this link.

34. ambbetten เเชร์เทคนิคในการทำเงินกับเกมสล็อตออนไลน์ เเจกสูตรสล็อตออนไลน์ที่อัพเดทใหม่ล่าสุด 2022 มีความเเม่ายำสูง เเนะนำเกมสล็อตออนไลน์น่าเล่น สำหรับคนทุนน้อย ข่าวสารวงการเกมเดิมพันออนไลน์รวมไว้ที่นี่เเล้ว สำหรับผู้ที่ชื่นชอบเกมเดิมพันออนไลน์ไม่ควรพลาดอย่างยิ่ง !!

35. like your all post. You have done really good work
Thank you for the information you provide, it helped me a lot. Thanks for Awesome tips Keep it up
Keep up the good work. And Thanks For Sharing

DecSoft App Builder Crack

Boom 3D Crack

Webroot SecureAnywhere Antivirus Crack

K7 Total Security Crack

36. Gutt Websäit : Zonahobisaya
Gutt Websäit : Zonahobisaya
Gutt Websäit : Zonahobisaya
Gutt Websäit : Resep
Gutt Websäit : Sinopsis Film
Gutt Websäit : Zonahobisaya
Gutt Websäit : Zonahobisaya
Gutt Websäit : Sinopsis Film

37. Thanks for sharing this post. Your work is amazing. You can also check out PicPick Professional Crack for Free. You can also visit the Website vcracks.com
PhpStorm Crack
Camtasia Studio Crack

38. I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here! keep up the good work...สล็อตออนไลน์

39. I really thank you for the valuable info on this great subject and look forward to more great posts. Thanks a lot for enjoying this beauty article with me. I am appreciating it very much! Looking forward to another great article. Good luck to the author! All the best!บา คา ร่า วอ เลท

40. I am very much pleased with the contents you have mentioned. I wanted to thank you for this great article.บา คา ร่า วอ เลท

41. I really loved reading your blog. It was very well authored and easy to understand. Unlike other blogs I have read which are really not that good.Thanks alot!สล็อตเว็บใหญ่

42. I have read a few of the articles on your website now, and I really like your style of blogging. I added it to my favorites blog site list and will be checking back soon. Please check out my site as well and let me know what you think.สล็อต ฝาก-ถอน true wallet ไม่มี บัญชีธนาคาร

43. You’ve got some interesting points in this article. I would have never considered any of these if I didn’t come across this. Thanks!.บาคาร่าวอเลท

44. What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very muchสล็อตวอเลท

45. Thank you so much for sharing this great blog.Very inspiring and helpful too.Hope you continue to share more of your ideas.I will definitely love to read.สล็อตxo

46. This comment has been removed by the author.

47. intriguing discussion may be worth comment. I’m sure you should write much more about this topic, may well be described as a taboo subject but generally folks are too little to chat on such topicsบาคาร่าออนไลน์