# Fuctorial map

**URL:** <https://discourse.ats-lang.org/t/fuctorial-map/206>\
**Category:** Google Group\
**Created:** [September 22, 2015, 4:12am UTC](https://discourse.ats-lang.org/t/fuctorial-map/206 "2015-09-22T04:12:19Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![Aistis\_Raulinaitis](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Aistis\_Raulinaitis](https://discourse.ats-lang.org/u/Aistis_Raulinaitis)\
**Post date:** [September 22, 2015, 4:12am UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/1 "2015-09-22T04:12:19Z")

</div>

Implementing F-Algebras in ATS, wondering what I’m doing wrong or where  
should I be looking? So far I have:

datatype Algebra (f:t@ype -\> t@ype,a:t@ype) = Algebra of (f a)

datatype Fix (f:t@ype -\> t@ype) = Iso of @{ invIso = f (Fix f) }

fun cata {f:t@ype -\> t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f -\> a) =  
lam (f) =\> alg (map (cata alg) (f.invIso))

The last line does compile, says that map is out of scope. Where would I  
get it? Mind you, f is a Functor.

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [September 23, 2015, 6:23pm UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/2 "2015-09-23T18:23:43Z")

</div>

If you compile to JavaScript, using t@ype is fine.  
However, if you do not use closures, you will encounter  
some compilation errors even if the code passes typechecking.On Wednesday, September 23, 2015 at 1:59:45 PM UTC-4, Aistis Raulinaitis wrote:

> Also:
> 
> extern fun fexpr\_eval : Algebra (Fexpr, int)
> 
> Sorry for the triple post!
> 
> So in all:
> 
> sortdef ftype = t@ype → t@ype
> 
> typedef Functor (f:ftype) = {a,b:t@ype} (a → b) → f a → f b
> 
> typedef Algebra (f:ftype, a:t@ype) = f a → a
> 
> datatype Fix (f:ftype) = Fx of f (Fix f)
> 
> extern fun fix\_unfold {f:ftype} : Fix f → f (Fix f)  
> implement fix\_unfold (Fx f) = f
> 
> extern fun cata : {f:ftype} {a:t@ype} Functor f → Algebra (f, a) → (Fix  
> f → a)  
> implement cata map = lam alg =\> lam f =\> alg (map (cata map alg) (fix\_unfold  
> f))
> 
> datatype Fexpr (a:t@ype)  
> = Int of int  
> | Add of (a, a)  
> | Mul of (a, a)
> 
> typedef Expr = Fix Fexpr
> 
> extern val fexpr\_map : Functor Fexpr  
> implement fexpr\_map f = lam e0 =\> ( case+ e0 of  
> | Int i =\> Int i  
> | Add (a, b) =\> Add (f a, f b)  
> | Mul (a, b) =\> Mul (f a, f b))
> 
> extern fun fexpr\_eval : Algebra (Fexpr, int)  
> implement fexpr\_eval e0 = ( case+ e0 of  
> | Int i =\> i  
> | Add (a, b) =\> a + b  
> | Mul (a, b) =\> a \* b)
> 
> val I1 = Fx (Int 1) : Expr  
> val I2 = Fx (Int 2) : Expr  
> val I3 = Fx (Int 3) : Expr  
> val Mul\_2\_3 = Fx (Mul (I2, I3)) : Expr  
> val Add\_1\_Mul\_2\_3 = Fx (Add (I1, Mul\_2\_3)) : Expr
> 
> val Ans = cata fexpr\_map fexpr\_eval Add\_1\_Mul\_2\_3
> 
> val () = println! ("eval(1+2\*3) = ", Ans)
> 
> implement main0 () = ()
> 
> On Monday, September 21, 2015 at 9:12:19 PM UTC-7, Aistis Raulinaitis wrote:
> 
> > Implementing F-Algebras in ATS, wondering what I’m doing wrong or where  
> > should I be looking? So far I have:
> > 
> > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > 
> > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > 
> > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a) =  
> > lam (f) =\> alg (map (cata alg) (f.invIso))
> > 
> > The last line does compile, says that map is out of scope. Where would I  
> > get it? Mind you, f is a Functor.

---

<div class="post-metadata">

**Author:** ![Aistis\_Raulinaitis](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Aistis\_Raulinaitis](https://discourse.ats-lang.org/u/Aistis_Raulinaitis)\
**Post date:** [September 23, 2015, 5:35pm UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/3 "2015-09-23T17:35:34Z")

</div>

Actually it’s a lot simpler, no need for Box, or cloref1, as well as you  
can implement it over t@ype. At least it typechecks…

sortdef ftype = t@ype → t@ype

typedef Functor (f:ftype) = {a,b:t@ype} (a → b) → f a → f b

typedef Algebra (f:ftype, a:t@ype) = f a → a

datatype Fix (f:ftype) = Fx of f (Fix f)

extern fun fix\_unfold {f:ftype} : Fix f → f (Fix f)  
implement fix\_unfold f = let val+ Fx f = f in f end

extern fun cata : {f:ftype}{a:t@ype} Functor f → Algebra (f, a) → (Fix f  
 → a)  
implement cata map = lam alg =\> lam f =\> alg (map (cata map alg) (fix\_unfold  
f))

datatype Fexpr (a:t@ype)  
= Int of int  
| Add of (a, a)  
| Mul of (a, a)

typedef Expr = Fix Fexpr

extern val fexpr\_map : Functor Fexpr  
implement fexpr\_map f = lam e0 =\> ( case+ e0 of  
| Int i =\> Int i  
| Add (a, b) =\> Add (f a, f b)  
| Mul (a, b) =\> Mul (f a, f b))

extern fun fexpr\_eval : Fexpr int → int  
implement fexpr\_eval e0 = ( case+ e0 of  
| Int i =\> i  
| Add (a, b) =\> a + b  
| Mul (a, b) =\> a \* b)

val I1 = Fx (Int 1): Expr  
val I2 = Fx (Int 2): Expr  
val I3 = Fx (Int 3): Expr  
val Mul\_2\_3 = Fx (Mul (I2, I3)): Expr  
val Add\_1\_Mul\_2\_3 = Fx (Add (I1, Mul\_2\_3)): Expr

val Ans = cata fexpr\_map fexpr\_eval Add\_1\_Mul\_2\_3

val () = println! ("eval(1+2\*3) = ", Ans)

implement main0 () = ()On Tuesday, September 22, 2015 at 10:41:05 AM UTC-7, gmhwxi wrote:

> This one works on-line:
> 
> [http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas\_serve.php?mycode\_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra\_js.dats](http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas_serve.php?mycode_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra_js.dats)
> 
> On Tuesday, September 22, 2015 at 1:01:51 PM UTC-4, Aistis Raulinaitis wrote:
> 
> > Beautiful! Thanks!
> > 
> > On Tue, Sep 22, 2015 at 7:22 AM, gmhwxi [gmh...@gmail.com](mailto:gmh...@gmail.com) wrote:
> > 
> > > For a bit fun, I get the F-algebra code running:
> > > 
> > > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats)
> > > 
> > > Well, it must be a bit crazy to program like this 🙂
> > > 
> > > On Tuesday, September 22, 2015 at 9:01:38 AM UTC-4, gmhwxi wrote:
> > > 
> > > > Here is something that typechecks:
> > > > 
> > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > //  
> > > > infixr (-\>) -\>\>  
> > > > //  
> > > > typedef  
> > > > -\>\> (a:type, b:type) = a - b  
> > > > //  
> > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > 
> > > > sortdef  
> > > > ftype = type → type  
> > > > typedef  
> > > > Algebra (f:ftype, a:type) = f(a) -\>\> a
> > > > 
> > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > //  
> > > > extern  
> > > > fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
> > > > //  
> > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > 
> > > > (\*  
> > > > datatype  
> > > > Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
> > > > \*)
> > > > 
> > > > abstype  
> > > > Fix(f:type → type)  
> > > > extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))
> > > > 
> > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > //  
> > > > fun  
> > > > cata{f:ftype}{a:type}  
> > > > (alg: Algebra (f,a)): (Fix f -\>\> a) =  
> > > > lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
> > > > //  
> > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > 
> > > > On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:
> > > > 
> > > > > Implementing F-Algebras in ATS, wondering what I’m doing wrong or  
> > > > > where should I be looking? So far I have:
> > > > > 
> > > > > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > > > > 
> > > > > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > > > > 
> > > > > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a)  
> > > > > = lam (f) =\> alg (map (cata alg) (f.invIso))
> > > > > 
> > > > > The last line does compile, says that map is out of scope. Where would  
> > > > > I get it? Mind you, f is a Functor.
> > > > 
> > > > –  
> > > > You received this message because you are subscribed to a topic in the  
> > > > Google Groups “ats-lang-users” group.  
> > > > To unsubscribe from this topic, visit  
> > > > [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe)  
> > > > .  
> > > > To unsubscribe from this group and all its topics, send an email to  
> > > > [ats-lang...@googlegroups.com](mailto:ats-lang...@googlegroups.com).  
> > > > To post to this group, send email to [ats-l...@googlegroups.com](mailto:ats-l...@googlegroups.com).  
> > > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > > To view this discussion on the web visit  
> > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com)  
> > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > > .

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [September 26, 2015, 3:13am UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/4 "2015-09-26T03:13:31Z")

</div>

This is due to a new feature ($d2ctype) being used in this example.

I have just uploaded a modified version that does not use this new feature.On Fri, Sep 25, 2015 at 11:01 PM, Aistis Raulinaitis [shega...@gmail.com](mailto:shega...@gmail.com) wrote:

> The typechecker complains with:
> 
> patsopt -tc -d  
> /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats  
> /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> 639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
> syntactic entity [s0taq] is needed.  
> /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> 639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
> syntactic entity [si0de] is needed.  
> /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> 639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
> syntactic entity [s0exp] is needed.  
> /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> 637(line=50, offs=5) – 638(line=50, offs=6): error(parsing): the keyword  
> [=] is needed.  
> /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> 629(line=49, offs=1) – 632(line=49, offs=4): error(parsing): the keyword  
> ‘}’ is needed.  
> /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> 610(line=46, offs=17) – 613(line=46, offs=20): error(parsing): the  
> syntactic entity [d0exp] is needed.  
> /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> 573(line=44, offs=1) – 582(line=44, offs=10): error(parsing): the token is  
> discarded.  
> exit(ATS): uncaught exception:  
> \_2home\_2hwxi\_2research\_2Postiats\_2git\_2src\_2pats\_error\_2esats\_\_FatalErrorExn(1025)
> 
> Compilation exited abnormally with code 1 at Fri Sep 25 19:57:55
> 
> On Thursday, September 24, 2015 at 7:30:29 PM UTC-7, gmhwxi wrote:
> 
> > I studied this cata-example a bit more.
> > 
> > As it stands now, this implementation is terribly slow.
> > 
> > I would like to suggest the following style of template-based  
> > implementation of cata:
> > 
> > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/TESTATS/catamorph.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/TESTATS/catamorph.dats)
> > 
> > I think it is quite involved to get the Haskell code (implementing  
> > F-algebra) to run efficiently.  
> > Cata(map) is clearly defined recursively and compiling it into efficient  
> > code likely needs to have  
> > deforestation optimization turned on.
> > 
> > The template-based implementation of cata in ATS does not create any  
> > trees, and there is no ‘Fix’  
> > clutter, either. All that is really needed for compiling the  
> > implementation into efficient code is to inline  
> > function calls aggressively.
> > 
> > On Wednesday, September 23, 2015 at 1:42:36 PM UTC-4, Aistis Raulinaitis wrote:
> > 
> > > The nice thing about F-algebras is that you can define fexpr\_eval  
> > > non-recursively. It’s quite fast, a lot of performant libs in Haskell are  
> > > written in terms of F-algebras. It’s especially good for languages that  
> > > don’t handle recursion well, and a succinct way of defining ASTs.
> > > 
> > > Also, you can simplify fix\_unfold:
> > > 
> > > extern fun fix\_unfold {f:ftype} : Fix f → f (Fix f)  
> > > implement fix\_unfold (Fx f) = f
> > > 
> > > On Tuesday, September 22, 2015 at 10:41:05 AM UTC-7, gmhwxi wrote:
> > > 
> > > > This one works on-line:
> > > > 
> > > > [http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas\_serve.php?mycode\_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra\_js.dats](http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas_serve.php?mycode_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra_js.dats)
> > > > 
> > > > On Tuesday, September 22, 2015 at 1:01:51 PM UTC-4, Aistis Raulinaitis wrote:
> > > > 
> > > > > Beautiful! Thanks!
> > > > > 
> > > > > On Tue, Sep 22, 2015 at 7:22 AM, gmhwxi [gmh...@gmail.com](mailto:gmh...@gmail.com) wrote:
> > > > > 
> > > > > > For a bit fun, I get the F-algebra code running:
> > > > > > 
> > > > > > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats)
> > > > > > 
> > > > > > Well, it must be a bit crazy to program like this 🙂
> > > > > > 
> > > > > > On Tuesday, September 22, 2015 at 9:01:38 AM UTC-4, gmhwxi wrote:
> > > > > > 
> > > > > > > Here is something that typechecks:
> > > > > > > 
> > > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > > //  
> > > > > > > infixr (-\>) -\>\>  
> > > > > > > //  
> > > > > > > typedef  
> > > > > > > -\>\> (a:type, b:type) = a - b  
> > > > > > > //  
> > > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > > 
> > > > > > > sortdef  
> > > > > > > ftype = type → type  
> > > > > > > typedef  
> > > > > > > Algebra (f:ftype, a:type) = f(a) -\>\> a
> > > > > > > 
> > > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > > //  
> > > > > > > extern  
> > > > > > > fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
> > > > > > > //  
> > > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > > 
> > > > > > > (\*  
> > > > > > > datatype  
> > > > > > > Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
> > > > > > > \*)
> > > > > > > 
> > > > > > > abstype  
> > > > > > > Fix(f:type → type)  
> > > > > > > extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))
> > > > > > > 
> > > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > > //  
> > > > > > > fun  
> > > > > > > cata{f:ftype}{a:type}  
> > > > > > > (alg: Algebra (f,a)): (Fix f -\>\> a) =  
> > > > > > > lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
> > > > > > > //  
> > > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > > 
> > > > > > > On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:
> > > > > > > 
> > > > > > > > Implementing F-Algebras in ATS, wondering what I’m doing wrong or  
> > > > > > > > where should I be looking? So far I have:
> > > > > > > > 
> > > > > > > > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > > > > > > > 
> > > > > > > > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > > > > > > > 
> > > > > > > > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f →   
> > > > > > > > a) = lam (f) =\> alg (map (cata alg) (f.invIso))
> > > > > > > > 
> > > > > > > > The last line does compile, says that map is out of scope. Where  
> > > > > > > > would I get it? Mind you, f is a Functor.
> > > > > > > 
> > > > > > > –  
> > > > > > > You received this message because you are subscribed to a topic in  
> > > > > > > the Google Groups “ats-lang-users” group.  
> > > > > > > To unsubscribe from this topic, visit  
> > > > > > > [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe)  
> > > > > > > .  
> > > > > > > To unsubscribe from this group and all its topics, send an email to  
> > > > > > > [ats-lang...@googlegroups.com](mailto:ats-lang...@googlegroups.com).  
> > > > > > > To post to this group, send email to [ats-l...@googlegroups.com](mailto:ats-l...@googlegroups.com).  
> > > > > > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > > > > > To view this discussion on the web visit  
> > > > > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com)  
> > > > > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > > > > > .
> > > > > 
> > > > > –  
> > > > > You received this message because you are subscribed to the Google Groups  
> > > > > “ats-lang-users” group.  
> > > > > To unsubscribe from this group and stop receiving emails from it, send an  
> > > > > email to [ats-lang-user...@googlegroups.com](mailto:ats-lang-user...@googlegroups.com).  
> > > > > To post to this group, send email to [ats-lan...@googlegroups.com](mailto:ats-lan...@googlegroups.com).  
> > > > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > > > To view this discussion on the web visit  
> > > > > [https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com)  
> > > > > [https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > > > .

---

<div class="post-metadata">

**Author:** ![Aistis\_Raulinaitis](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Aistis\_Raulinaitis](https://discourse.ats-lang.org/u/Aistis_Raulinaitis)\
**Post date:** [September 26, 2015, 3:44am UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/5 "2015-09-26T03:44:59Z")

</div>

Interesting, what does $d2ctype do?On Fri, Sep 25, 2015 at 8:13 PM, Hongwei Xi [gmh...@gmail.com](mailto:gmh...@gmail.com) wrote:

> This is due to a new feature ($d2ctype) being used in this example.
> 
> I have just uploaded a modified version that does not use this new feature.
> 
> On Fri, Sep 25, 2015 at 11:01 PM, Aistis Raulinaitis \< [shega...@gmail.com](mailto:shega...@gmail.com)\> wrote:
> 
> > The typechecker complains with:
> > 
> > patsopt -tc -d  
> > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats  
> > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > 639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
> > syntactic entity [s0taq] is needed.  
> > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > 639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
> > syntactic entity [si0de] is needed.  
> > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > 639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
> > syntactic entity [s0exp] is needed.  
> > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > 637(line=50, offs=5) – 638(line=50, offs=6): error(parsing): the keyword  
> > [=] is needed.  
> > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > 629(line=49, offs=1) – 632(line=49, offs=4): error(parsing): the keyword  
> > ‘}’ is needed.  
> > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > 610(line=46, offs=17) – 613(line=46, offs=20): error(parsing): the  
> > syntactic entity [d0exp] is needed.  
> > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > 573(line=44, offs=1) – 582(line=44, offs=10): error(parsing): the token is  
> > discarded.  
> > exit(ATS): uncaught exception:  
> > \_2home\_2hwxi\_2research\_2Postiats\_2git\_2src\_2pats\_error\_2esats\_\_FatalErrorExn(1025)
> > 
> > Compilation exited abnormally with code 1 at Fri Sep 25 19:57:55
> > 
> > On Thursday, September 24, 2015 at 7:30:29 PM UTC-7, gmhwxi wrote:
> > 
> > > I studied this cata-example a bit more.
> > > 
> > > As it stands now, this implementation is terribly slow.
> > > 
> > > I would like to suggest the following style of template-based  
> > > implementation of cata:
> > > 
> > > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/TESTATS/catamorph.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/TESTATS/catamorph.dats)
> > > 
> > > I think it is quite involved to get the Haskell code (implementing  
> > > F-algebra) to run efficiently.  
> > > Cata(map) is clearly defined recursively and compiling it into efficient  
> > > code likely needs to have  
> > > deforestation optimization turned on.
> > > 
> > > The template-based implementation of cata in ATS does not create any  
> > > trees, and there is no ‘Fix’  
> > > clutter, either. All that is really needed for compiling the  
> > > implementation into efficient code is to inline  
> > > function calls aggressively.
> > > 
> > > On Wednesday, September 23, 2015 at 1:42:36 PM UTC-4, Aistis Raulinaitis wrote:
> > > 
> > > > The nice thing about F-algebras is that you can define fexpr\_eval  
> > > > non-recursively. It’s quite fast, a lot of performant libs in Haskell are  
> > > > written in terms of F-algebras. It’s especially good for languages that  
> > > > don’t handle recursion well, and a succinct way of defining ASTs.
> > > > 
> > > > Also, you can simplify fix\_unfold:
> > > > 
> > > > extern fun fix\_unfold {f:ftype} : Fix f → f (Fix f)  
> > > > implement fix\_unfold (Fx f) = f
> > > > 
> > > > On Tuesday, September 22, 2015 at 10:41:05 AM UTC-7, gmhwxi wrote:
> > > > 
> > > > > This one works on-line:
> > > > > 
> > > > > [http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas\_serve.php?mycode\_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra\_js.dats](http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas_serve.php?mycode_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra_js.dats)
> > > > > 
> > > > > On Tuesday, September 22, 2015 at 1:01:51 PM UTC-4, Aistis Raulinaitis wrote:
> > > > > 
> > > > > > Beautiful! Thanks!
> > > > > > 
> > > > > > On Tue, Sep 22, 2015 at 7:22 AM, gmhwxi [gmh...@gmail.com](mailto:gmh...@gmail.com) wrote:
> > > > > > 
> > > > > > > For a bit fun, I get the F-algebra code running:
> > > > > > > 
> > > > > > > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats)
> > > > > > > 
> > > > > > > Well, it must be a bit crazy to program like this 🙂
> > > > > > > 
> > > > > > > On Tuesday, September 22, 2015 at 9:01:38 AM UTC-4, gmhwxi wrote:
> > > > > > > 
> > > > > > > > Here is something that typechecks:
> > > > > > > > 
> > > > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > > > //  
> > > > > > > > infixr (-\>) -\>\>  
> > > > > > > > //  
> > > > > > > > typedef  
> > > > > > > > -\>\> (a:type, b:type) = a - b  
> > > > > > > > //  
> > > > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > > > 
> > > > > > > > sortdef  
> > > > > > > > ftype = type → type  
> > > > > > > > typedef  
> > > > > > > > Algebra (f:ftype, a:type) = f(a) -\>\> a
> > > > > > > > 
> > > > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > > > //  
> > > > > > > > extern  
> > > > > > > > fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
> > > > > > > > //  
> > > > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > > > 
> > > > > > > > (\*  
> > > > > > > > datatype  
> > > > > > > > Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
> > > > > > > > \*)
> > > > > > > > 
> > > > > > > > abstype  
> > > > > > > > Fix(f:type → type)  
> > > > > > > > extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))
> > > > > > > > 
> > > > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > > > //  
> > > > > > > > fun  
> > > > > > > > cata{f:ftype}{a:type}  
> > > > > > > > (alg: Algebra (f,a)): (Fix f -\>\> a) =  
> > > > > > > > lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
> > > > > > > > //  
> > > > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > > > 
> > > > > > > > On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:
> > > > > > > > 
> > > > > > > > > Implementing F-Algebras in ATS, wondering what I’m doing wrong or  
> > > > > > > > > where should I be looking? So far I have:
> > > > > > > > > 
> > > > > > > > > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > > > > > > > > 
> > > > > > > > > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > > > > > > > > 
> > > > > > > > > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f  
> > > > > > > > > → a) = lam (f) =\> alg (map (cata alg) (f.invIso))
> > > > > > > > > 
> > > > > > > > > The last line does compile, says that map is out of scope. Where  
> > > > > > > > > would I get it? Mind you, f is a Functor.
> > > > > > > > 
> > > > > > > > –  
> > > > > > > > You received this message because you are subscribed to a topic in  
> > > > > > > > the Google Groups “ats-lang-users” group.  
> > > > > > > > To unsubscribe from this topic, visit  
> > > > > > > > [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe)  
> > > > > > > > .  
> > > > > > > > To unsubscribe from this group and all its topics, send an email to  
> > > > > > > > [ats-lang...@googlegroups.com](mailto:ats-lang...@googlegroups.com).  
> > > > > > > > To post to this group, send email to [ats-l...@googlegroups.com](mailto:ats-l...@googlegroups.com).  
> > > > > > > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > > > > > > To view this discussion on the web visit  
> > > > > > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com)  
> > > > > > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > > > > > > .
> > > > > > 
> > > > > > –  
> > > > > > You received this message because you are subscribed to the Google Groups  
> > > > > > “ats-lang-users” group.  
> > > > > > To unsubscribe from this group and stop receiving emails from it, send an  
> > > > > > email to [ats-lang-user...@googlegroups.com](mailto:ats-lang-user...@googlegroups.com).  
> > > > > > To post to this group, send email to [ats-lan...@googlegroups.com](mailto:ats-lan...@googlegroups.com).  
> > > > > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > > > > To view this discussion on the web visit  
> > > > > > [https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com)  
> > > > > > [https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > > > > .
> 
> –  
> You received this message because you are subscribed to a topic in the  
> Google Groups “ats-lang-users” group.  
> To unsubscribe from this topic, visit  
> [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe).  
> To unsubscribe from this group and all its topics, send an email to  
> [ats-lang-user...@googlegroups.com](mailto:ats-lang-user...@googlegroups.com).  
> To post to this group, send email to [ats-lan...@googlegroups.com](mailto:ats-lan...@googlegroups.com).  
> Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> To view this discussion on the web visit  
> [https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLqU6hSBn9mmjRpoy%3DXA1rZq8YMvzWYkMnfB7uuSu73AAA%40mail.gmail.com](https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLqU6hSBn9mmjRpoy%3DXA1rZq8YMvzWYkMnfB7uuSu73AAA%40mail.gmail.com)  
> [https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLqU6hSBn9mmjRpoy%3DXA1rZq8YMvzWYkMnfB7uuSu73AAA%40mail.gmail.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLqU6hSBn9mmjRpoy%3DXA1rZq8YMvzWYkMnfB7uuSu73AAA%40mail.gmail.com?utm_medium=email&utm_source=footer)  
> .

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [September 22, 2015, 11:11am UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/6 "2015-09-22T11:11:08Z")

</div>

At one point implemented Yoneda lemma and co-Yoneda lemma:

> <https://github.com/githwxi/ATS-Postiats/tree/master/doc/EXAMPLE/ATSLF>
>
> //github.com/githwxi/ATS-Postiats/tree/master/doc/EXAMPLE/ATSLF

I remember that I had to use type instead of t@ype.On Tuesday, September 22, 2015 at 12:44:31 AM UTC-4, Aistis Raulinaitis wrote:

> Also yes, Algebra should be defined as:
> 
> typedef Algebra (f:t@ype → t@ype,a:t@ype) = f a → a
> 
> I don’t know what I copied…
> 
> On Monday, September 21, 2015 at 9:12:19 PM UTC-7, Aistis Raulinaitis wrote:
> 
> > Implementing F-Algebras in ATS, wondering what I’m doing wrong or where  
> > should I be looking? So far I have:
> > 
> > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > 
> > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > 
> > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a) =  
> > lam (f) =\> alg (map (cata alg) (f.invIso))
> > 
> > The last line does compile, says that map is out of scope. Where would I  
> > get it? Mind you, f is a Functor.

---

<div class="post-metadata">

**Author:** ![Aistis\_Raulinaitis](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Aistis\_Raulinaitis](https://discourse.ats-lang.org/u/Aistis_Raulinaitis)\
**Post date:** [September 22, 2015, 5:01pm UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/7 "2015-09-22T17:01:30Z")

</div>

Beautiful! Thanks!On Tue, Sep 22, 2015 at 7:22 AM, gmhwxi [gmh...@gmail.com](mailto:gmh...@gmail.com) wrote:

> For a bit fun, I get the F-algebra code running:
> 
> [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats)
> 
> Well, it must be a bit crazy to program like this 🙂
> 
> On Tuesday, September 22, 2015 at 9:01:38 AM UTC-4, gmhwxi wrote:
> 
> > Here is something that typechecks:
> > 
> > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > //  
> > infixr (-\>) -\>\>  
> > //  
> > typedef  
> > -\>\> (a:type, b:type) = a - b  
> > //  
> > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > 
> > sortdef  
> > ftype = type → type  
> > typedef  
> > Algebra (f:ftype, a:type) = f(a) -\>\> a
> > 
> > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > //  
> > extern  
> > fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
> > //  
> > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > 
> > (\*  
> > datatype  
> > Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
> > \*)
> > 
> > abstype  
> > Fix(f:type → type)  
> > extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))
> > 
> > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > //  
> > fun  
> > cata{f:ftype}{a:type}  
> > (alg: Algebra (f,a)): (Fix f -\>\> a) =  
> > lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
> > //  
> > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > 
> > On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:
> > 
> > > Implementing F-Algebras in ATS, wondering what I’m doing wrong or where  
> > > should I be looking? So far I have:
> > > 
> > > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > > 
> > > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > > 
> > > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a) =  
> > > lam (f) =\> alg (map (cata alg) (f.invIso))
> > > 
> > > The last line does compile, says that map is out of scope. Where would I  
> > > get it? Mind you, f is a Functor.
> > 
> > –  
> > You received this message because you are subscribed to a topic in the  
> > Google Groups “ats-lang-users” group.  
> > To unsubscribe from this topic, visit  
> > [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe).  
> > To unsubscribe from this group and all its topics, send an email to  
> > [ats-lang-user...@googlegroups.com](mailto:ats-lang-user...@googlegroups.com).  
> > To post to this group, send email to [ats-lan...@googlegroups.com](mailto:ats-lan...@googlegroups.com).  
> > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > To view this discussion on the web visit  
> > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com)  
> > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > .

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [September 22, 2015, 5:41pm UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/8 "2015-09-22T17:41:04Z")

</div>

This one works on-line:

[http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas\_serve.php?mycode\_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra\_js.datsOn](http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas_serve.php?mycode_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra_js.datsOn) Tuesday, September 22, 2015 at 1:01:51 PM UTC-4, Aistis Raulinaitis wrote:

> Beautiful! Thanks!
> 
> On Tue, Sep 22, 2015 at 7:22 AM, gmhwxi \<[gmh...@gmail.com](mailto:gmh...@gmail.com) \<javascript:\>\> wrote:
> 
> > For a bit fun, I get the F-algebra code running:
> > 
> > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats)
> > 
> > Well, it must be a bit crazy to program like this 🙂
> > 
> > On Tuesday, September 22, 2015 at 9:01:38 AM UTC-4, gmhwxi wrote:
> > 
> > > Here is something that typechecks:
> > > 
> > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > //  
> > > infixr (-\>) -\>\>  
> > > //  
> > > typedef  
> > > -\>\> (a:type, b:type) = a - b  
> > > //  
> > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > 
> > > sortdef  
> > > ftype = type → type  
> > > typedef  
> > > Algebra (f:ftype, a:type) = f(a) -\>\> a
> > > 
> > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > //  
> > > extern  
> > > fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
> > > //  
> > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > 
> > > (\*  
> > > datatype  
> > > Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
> > > \*)
> > > 
> > > abstype  
> > > Fix(f:type → type)  
> > > extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))
> > > 
> > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > //  
> > > fun  
> > > cata{f:ftype}{a:type}  
> > > (alg: Algebra (f,a)): (Fix f -\>\> a) =  
> > > lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
> > > //  
> > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > 
> > > On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:
> > > 
> > > > Implementing F-Algebras in ATS, wondering what I’m doing wrong or where  
> > > > should I be looking? So far I have:
> > > > 
> > > > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > > > 
> > > > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > > > 
> > > > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a)  
> > > > = lam (f) =\> alg (map (cata alg) (f.invIso))
> > > > 
> > > > The last line does compile, says that map is out of scope. Where would  
> > > > I get it? Mind you, f is a Functor.
> > > 
> > > –  
> > > You received this message because you are subscribed to a topic in the  
> > > Google Groups “ats-lang-users” group.  
> > > To unsubscribe from this topic, visit  
> > > [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe).  
> > > To unsubscribe from this group and all its topics, send an email to  
> > > [ats-lang...@googlegroups.com](mailto:ats-lang...@googlegroups.com) \<javascript:\>.  
> > > To post to this group, send email to [ats-l...@googlegroups.com](mailto:ats-l...@googlegroups.com)  
> > > \<javascript:\>.  
> > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > To view this discussion on the web visit  
> > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com)  
> > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > .

---

<div class="post-metadata">

**Author:** ![Aistis\_Raulinaitis](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Aistis\_Raulinaitis](https://discourse.ats-lang.org/u/Aistis_Raulinaitis)\
**Post date:** [September 22, 2015, 4:44am UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/9 "2015-09-22T04:44:30Z")

</div>

Also yes, Algebra should be defined as:

typedef Algebra (f:t@ype → t@ype,a:t@ype) = f a → a

I don’t know what I copied…On Monday, September 21, 2015 at 9:12:19 PM UTC-7, Aistis Raulinaitis wrote:

> Implementing F-Algebras in ATS, wondering what I’m doing wrong or where  
> should I be looking? So far I have:
> 
> datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> 
> datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> 
> fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a) =  
> lam (f) =\> alg (map (cata alg) (f.invIso))
> 
> The last line does compile, says that map is out of scope. Where would I  
> get it? Mind you, f is a Functor.

---

<div class="post-metadata">

**Author:** ![Aistis\_Raulinaitis](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Aistis\_Raulinaitis](https://discourse.ats-lang.org/u/Aistis_Raulinaitis)\
**Post date:** [September 23, 2015, 5:42pm UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/10 "2015-09-23T17:42:36Z")

</div>

The nice thing about F-algebras is that you can define fexpr\_eval  
non-recursively. It’s quite fast, a lot of performant libs in Haskell are  
written in terms of F-algebras. It’s especially good for languages that  
don’t handle recursion well, and a succinct way of defining ASTs.

Also, you can simplify fix\_unfold:

extern fun fix\_unfold {f:ftype} : Fix f → f (Fix f)  
implement fix\_unfold (Fx f) = fOn Tuesday, September 22, 2015 at 10:41:05 AM UTC-7, gmhwxi wrote:

> This one works on-line:
> 
> [http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas\_serve.php?mycode\_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra\_js.dats](http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas_serve.php?mycode_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra_js.dats)
> 
> On Tuesday, September 22, 2015 at 1:01:51 PM UTC-4, Aistis Raulinaitis wrote:
> 
> > Beautiful! Thanks!
> > 
> > On Tue, Sep 22, 2015 at 7:22 AM, gmhwxi [gmh...@gmail.com](mailto:gmh...@gmail.com) wrote:
> > 
> > > For a bit fun, I get the F-algebra code running:
> > > 
> > > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats)
> > > 
> > > Well, it must be a bit crazy to program like this 🙂
> > > 
> > > On Tuesday, September 22, 2015 at 9:01:38 AM UTC-4, gmhwxi wrote:
> > > 
> > > > Here is something that typechecks:
> > > > 
> > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > //  
> > > > infixr (-\>) -\>\>  
> > > > //  
> > > > typedef  
> > > > -\>\> (a:type, b:type) = a - b  
> > > > //  
> > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > 
> > > > sortdef  
> > > > ftype = type → type  
> > > > typedef  
> > > > Algebra (f:ftype, a:type) = f(a) -\>\> a
> > > > 
> > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > //  
> > > > extern  
> > > > fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
> > > > //  
> > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > 
> > > > (\*  
> > > > datatype  
> > > > Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
> > > > \*)
> > > > 
> > > > abstype  
> > > > Fix(f:type → type)  
> > > > extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))
> > > > 
> > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > //  
> > > > fun  
> > > > cata{f:ftype}{a:type}  
> > > > (alg: Algebra (f,a)): (Fix f -\>\> a) =  
> > > > lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
> > > > //  
> > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > 
> > > > On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:
> > > > 
> > > > > Implementing F-Algebras in ATS, wondering what I’m doing wrong or  
> > > > > where should I be looking? So far I have:
> > > > > 
> > > > > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > > > > 
> > > > > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > > > > 
> > > > > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a)  
> > > > > = lam (f) =\> alg (map (cata alg) (f.invIso))
> > > > > 
> > > > > The last line does compile, says that map is out of scope. Where would  
> > > > > I get it? Mind you, f is a Functor.
> > > > 
> > > > –  
> > > > You received this message because you are subscribed to a topic in the  
> > > > Google Groups “ats-lang-users” group.  
> > > > To unsubscribe from this topic, visit  
> > > > [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe)  
> > > > .  
> > > > To unsubscribe from this group and all its topics, send an email to  
> > > > [ats-lang...@googlegroups.com](mailto:ats-lang...@googlegroups.com).  
> > > > To post to this group, send email to [ats-l...@googlegroups.com](mailto:ats-l...@googlegroups.com).  
> > > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > > To view this discussion on the web visit  
> > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com)  
> > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > > .

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [September 22, 2015, 1:01pm UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/11 "2015-09-22T13:01:38Z")

</div>

Here is something that typechecks:

(\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
//  
infixr (-\>) -\>\>  
//  
typedef  
-\>\> (a:type, b:type) = a - b  
//  
(_ \*\*\*\*\*\* \*\*\*\*\*\* \*)

sortdef  
ftype = type → type  
typedef  
Algebra (f:ftype, a:type) = f(a) -\>\> a

(\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
//  
extern  
fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
//  
(_ \*\*\*\*\*\* \*\*\*\*\*\* \*)

(\*  
datatype  
Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
\*)

abstype  
Fix(f:type → type)  
extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))

(\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
//  
fun  
cata{f:ftype}{a:type}  
(alg: Algebra (f,a)): (Fix f -\>\> a) =  
lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
//  
(_ \*\*\*\*\*\* \*\*\*\*\*\* \*)On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:

> Implementing F-Algebras in ATS, wondering what I’m doing wrong or where  
> should I be looking? So far I have:
> 
> datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> 
> datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> 
> fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a) =  
> lam (f) =\> alg (map (cata alg) (f.invIso))
> 
> The last line does compile, says that map is out of scope. Where would I  
> get it? Mind you, f is a Functor.

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [September 25, 2015, 2:30am UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/12 "2015-09-25T02:30:28Z")

</div>

I studied this cata-example a bit more.

As it stands now, this implementation is terribly slow.

I would like to suggest the following style of template-based  
implementation of cata:

> <https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/TESTATS/catamorph.dats>

I think it is quite involved to get the Haskell code (implementing  
F-algebra) to run efficiently.  
Cata(map) is clearly defined recursively and compiling it into efficient  
code likely needs to have  
deforestation optimization turned on.

The template-based implementation of cata in ATS does not create any trees,  
and there is no ‘Fix’  
clutter, either. All that is really needed for compiling the implementation  
into efficient code is to inline  
function calls aggressively.On Wednesday, September 23, 2015 at 1:42:36 PM UTC-4, Aistis Raulinaitis wrote:

> The nice thing about F-algebras is that you can define fexpr\_eval  
> non-recursively. It’s quite fast, a lot of performant libs in Haskell are  
> written in terms of F-algebras. It’s especially good for languages that  
> don’t handle recursion well, and a succinct way of defining ASTs.
> 
> Also, you can simplify fix\_unfold:
> 
> extern fun fix\_unfold {f:ftype} : Fix f → f (Fix f)  
> implement fix\_unfold (Fx f) = f
> 
> On Tuesday, September 22, 2015 at 10:41:05 AM UTC-7, gmhwxi wrote:
> 
> > This one works on-line:
> > 
> > [http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas\_serve.php?mycode\_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra\_js.dats](http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas_serve.php?mycode_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra_js.dats)
> > 
> > On Tuesday, September 22, 2015 at 1:01:51 PM UTC-4, Aistis Raulinaitis wrote:
> > 
> > > Beautiful! Thanks!
> > > 
> > > On Tue, Sep 22, 2015 at 7:22 AM, gmhwxi [gmh...@gmail.com](mailto:gmh...@gmail.com) wrote:
> > > 
> > > > For a bit fun, I get the F-algebra code running:
> > > > 
> > > > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats)
> > > > 
> > > > Well, it must be a bit crazy to program like this 🙂
> > > > 
> > > > On Tuesday, September 22, 2015 at 9:01:38 AM UTC-4, gmhwxi wrote:
> > > > 
> > > > > Here is something that typechecks:
> > > > > 
> > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > //  
> > > > > infixr (-\>) -\>\>  
> > > > > //  
> > > > > typedef  
> > > > > -\>\> (a:type, b:type) = a - b  
> > > > > //  
> > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > 
> > > > > sortdef  
> > > > > ftype = type → type  
> > > > > typedef  
> > > > > Algebra (f:ftype, a:type) = f(a) -\>\> a
> > > > > 
> > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > //  
> > > > > extern  
> > > > > fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
> > > > > //  
> > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > 
> > > > > (\*  
> > > > > datatype  
> > > > > Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
> > > > > \*)
> > > > > 
> > > > > abstype  
> > > > > Fix(f:type → type)  
> > > > > extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))
> > > > > 
> > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > //  
> > > > > fun  
> > > > > cata{f:ftype}{a:type}  
> > > > > (alg: Algebra (f,a)): (Fix f -\>\> a) =  
> > > > > lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
> > > > > //  
> > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > 
> > > > > On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:
> > > > > 
> > > > > > Implementing F-Algebras in ATS, wondering what I’m doing wrong or  
> > > > > > where should I be looking? So far I have:
> > > > > > 
> > > > > > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > > > > > 
> > > > > > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > > > > > 
> > > > > > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a  
> > > > > > ) = lam (f) =\> alg (map (cata alg) (f.invIso))
> > > > > > 
> > > > > > The last line does compile, says that map is out of scope. Where  
> > > > > > would I get it? Mind you, f is a Functor.
> > > > > 
> > > > > –  
> > > > > You received this message because you are subscribed to a topic in the  
> > > > > Google Groups “ats-lang-users” group.  
> > > > > To unsubscribe from this topic, visit  
> > > > > [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe)  
> > > > > .  
> > > > > To unsubscribe from this group and all its topics, send an email to  
> > > > > [ats-lang...@googlegroups.com](mailto:ats-lang...@googlegroups.com).  
> > > > > To post to this group, send email to [ats-l...@googlegroups.com](mailto:ats-l...@googlegroups.com).  
> > > > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > > > To view this discussion on the web visit  
> > > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com)  
> > > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > > > .

---

<div class="post-metadata">

**Author:** ![Aistis\_Raulinaitis](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Aistis\_Raulinaitis](https://discourse.ats-lang.org/u/Aistis_Raulinaitis)\
**Post date:** [September 23, 2015, 5:59pm UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/13 "2015-09-23T17:59:45Z")

</div>

Also:

extern fun fexpr\_eval : Algebra (Fexpr, int)

Sorry for the triple post!

So in all:

sortdef ftype = t@ype → t@ype

typedef Functor (f:ftype) = {a,b:t@ype} (a → b) → f a → f b

typedef Algebra (f:ftype, a:t@ype) = f a → a

datatype Fix (f:ftype) = Fx of f (Fix f)

extern fun fix\_unfold {f:ftype} : Fix f → f (Fix f)  
implement fix\_unfold (Fx f) = f

extern fun cata : {f:ftype} {a:t@ype} Functor f → Algebra (f, a) → (Fix f  
 → a)  
implement cata map = lam alg =\> lam f =\> alg (map (cata map alg) (fix\_unfold  
f))

datatype Fexpr (a:t@ype)  
= Int of int  
| Add of (a, a)  
| Mul of (a, a)

typedef Expr = Fix Fexpr

extern val fexpr\_map : Functor Fexpr  
implement fexpr\_map f = lam e0 =\> ( case+ e0 of  
| Int i =\> Int i  
| Add (a, b) =\> Add (f a, f b)  
| Mul (a, b) =\> Mul (f a, f b))

extern fun fexpr\_eval : Algebra (Fexpr, int)  
implement fexpr\_eval e0 = ( case+ e0 of  
| Int i =\> i  
| Add (a, b) =\> a + b  
| Mul (a, b) =\> a \* b)

val I1 = Fx (Int 1) : Expr  
val I2 = Fx (Int 2) : Expr  
val I3 = Fx (Int 3) : Expr  
val Mul\_2\_3 = Fx (Mul (I2, I3)) : Expr  
val Add\_1\_Mul\_2\_3 = Fx (Add (I1, Mul\_2\_3)) : Expr

val Ans = cata fexpr\_map fexpr\_eval Add\_1\_Mul\_2\_3

val () = println! ("eval(1+2\*3) = ", Ans)

implement main0 () = ()On Monday, September 21, 2015 at 9:12:19 PM UTC-7, Aistis Raulinaitis wrote:

> Implementing F-Algebras in ATS, wondering what I’m doing wrong or where  
> should I be looking? So far I have:
> 
> datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> 
> datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> 
> fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a) =  
> lam (f) =\> alg (map (cata alg) (f.invIso))
> 
> The last line does compile, says that map is out of scope. Where would I  
> get it? Mind you, f is a Functor.

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [September 26, 2015, 10:57am UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/14 "2015-09-26T10:57:08Z")

</div>

See the following link for some explanation on $d2ctype:

[Redirecting to Google Groups](https://groups.google.com/forum/#!topic/ats-lang-users/lK9WrvIT5i8On) Friday, September 25, 2015 at 11:45:19 PM UTC-4, Aistis Raulinaitis wrote:

> Interesting, what does $d2ctype do?
> 
> On Fri, Sep 25, 2015 at 8:13 PM, Hongwei Xi \<[gmh...@gmail.com](mailto:gmh...@gmail.com) \<javascript:\>\> wrote:
> 
> > This is due to a new feature ($d2ctype) being used in this example.
> > 
> > I have just uploaded a modified version that does not use this new  
> > feature.
> > 
> > On Fri, Sep 25, 2015 at 11:01 PM, Aistis Raulinaitis \<[sheg...@gmail.com](mailto:sheg...@gmail.com) \<javascript:\>\> wrote:
> > 
> > > The typechecker complains with:
> > > 
> > > patsopt -tc -d  
> > > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats  
> > > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > > 639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
> > > syntactic entity [s0taq] is needed.  
> > > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > > 639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
> > > syntactic entity [si0de] is needed.  
> > > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > > 639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
> > > syntactic entity [s0exp] is needed.  
> > > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > > 637(line=50, offs=5) – 638(line=50, offs=6): error(parsing): the keyword  
> > > [=] is needed.  
> > > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > > 629(line=49, offs=1) – 632(line=49, offs=4): error(parsing): the keyword  
> > > ‘}’ is needed.  
> > > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > > 610(line=46, offs=17) – 613(line=46, offs=20): error(parsing): the  
> > > syntactic entity [d0exp] is needed.  
> > > /home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
> > > 573(line=44, offs=1) – 582(line=44, offs=10): error(parsing): the token is  
> > > discarded.  
> > > exit(ATS): uncaught exception:  
> > > \_2home\_2hwxi\_2research\_2Postiats\_2git\_2src\_2pats\_error\_2esats\_\_FatalErrorExn(1025)
> > > 
> > > Compilation exited abnormally with code 1 at Fri Sep 25 19:57:55
> > > 
> > > On Thursday, September 24, 2015 at 7:30:29 PM UTC-7, gmhwxi wrote:
> > > 
> > > > I studied this cata-example a bit more.
> > > > 
> > > > As it stands now, this implementation is terribly slow.
> > > > 
> > > > I would like to suggest the following style of template-based  
> > > > implementation of cata:
> > > > 
> > > > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/TESTATS/catamorph.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/TESTATS/catamorph.dats)
> > > > 
> > > > I think it is quite involved to get the Haskell code (implementing  
> > > > F-algebra) to run efficiently.  
> > > > Cata(map) is clearly defined recursively and compiling it into  
> > > > efficient code likely needs to have  
> > > > deforestation optimization turned on.
> > > > 
> > > > The template-based implementation of cata in ATS does not create any  
> > > > trees, and there is no ‘Fix’  
> > > > clutter, either. All that is really needed for compiling the  
> > > > implementation into efficient code is to inline  
> > > > function calls aggressively.
> > > > 
> > > > On Wednesday, September 23, 2015 at 1:42:36 PM UTC-4, Aistis Raulinaitis wrote:
> > > > 
> > > > > The nice thing about F-algebras is that you can define fexpr\_eval  
> > > > > non-recursively. It’s quite fast, a lot of performant libs in Haskell are  
> > > > > written in terms of F-algebras. It’s especially good for languages that  
> > > > > don’t handle recursion well, and a succinct way of defining ASTs.
> > > > > 
> > > > > Also, you can simplify fix\_unfold:
> > > > > 
> > > > > extern fun fix\_unfold {f:ftype} : Fix f → f (Fix f)  
> > > > > implement fix\_unfold (Fx f) = f
> > > > > 
> > > > > On Tuesday, September 22, 2015 at 10:41:05 AM UTC-7, gmhwxi wrote:
> > > > > 
> > > > > > This one works on-line:
> > > > > > 
> > > > > > [http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas\_serve.php?mycode\_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra\_js.dats](http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas_serve.php?mycode_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra_js.dats)
> > > > > > 
> > > > > > On Tuesday, September 22, 2015 at 1:01:51 PM UTC-4, Aistis Raulinaitis wrote:
> > > > > > 
> > > > > > > Beautiful! Thanks!
> > > > > > > 
> > > > > > > On Tue, Sep 22, 2015 at 7:22 AM, gmhwxi [gmh...@gmail.com](mailto:gmh...@gmail.com) wrote:
> > > > > > > 
> > > > > > > > For a bit fun, I get the F-algebra code running:
> > > > > > > > 
> > > > > > > > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats)
> > > > > > > > 
> > > > > > > > Well, it must be a bit crazy to program like this 🙂
> > > > > > > > 
> > > > > > > > On Tuesday, September 22, 2015 at 9:01:38 AM UTC-4, gmhwxi wrote:
> > > > > > > > 
> > > > > > > > > Here is something that typechecks:
> > > > > > > > > 
> > > > > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > > > > //  
> > > > > > > > > infixr (-\>) -\>\>  
> > > > > > > > > //  
> > > > > > > > > typedef  
> > > > > > > > > -\>\> (a:type, b:type) = a - b  
> > > > > > > > > //  
> > > > > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > > > > 
> > > > > > > > > sortdef  
> > > > > > > > > ftype = type → type  
> > > > > > > > > typedef  
> > > > > > > > > Algebra (f:ftype, a:type) = f(a) -\>\> a
> > > > > > > > > 
> > > > > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > > > > //  
> > > > > > > > > extern  
> > > > > > > > > fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
> > > > > > > > > //  
> > > > > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > > > > 
> > > > > > > > > (\*  
> > > > > > > > > datatype  
> > > > > > > > > Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
> > > > > > > > > \*)
> > > > > > > > > 
> > > > > > > > > abstype  
> > > > > > > > > Fix(f:type → type)  
> > > > > > > > > extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))
> > > > > > > > > 
> > > > > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > > > > //  
> > > > > > > > > fun  
> > > > > > > > > cata{f:ftype}{a:type}  
> > > > > > > > > (alg: Algebra (f,a)): (Fix f -\>\> a) =  
> > > > > > > > > lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
> > > > > > > > > //  
> > > > > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > > > > 
> > > > > > > > > On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:
> > > > > > > > > 
> > > > > > > > > > Implementing F-Algebras in ATS, wondering what I’m doing wrong or  
> > > > > > > > > > where should I be looking? So far I have:
> > > > > > > > > > 
> > > > > > > > > > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > > > > > > > > > 
> > > > > > > > > > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > > > > > > > > > 
> > > > > > > > > > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f  
> > > > > > > > > > → a) = lam (f) =\> alg (map (cata alg) (f.invIso))
> > > > > > > > > > 
> > > > > > > > > > The last line does compile, says that map is out of scope. Where  
> > > > > > > > > > would I get it? Mind you, f is a Functor.
> > > > > > > > > 
> > > > > > > > > –  
> > > > > > > > > You received this message because you are subscribed to a topic in  
> > > > > > > > > the Google Groups “ats-lang-users” group.  
> > > > > > > > > To unsubscribe from this topic, visit  
> > > > > > > > > [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe)  
> > > > > > > > > .  
> > > > > > > > > To unsubscribe from this group and all its topics, send an email to  
> > > > > > > > > [ats-lang...@googlegroups.com](mailto:ats-lang...@googlegroups.com).  
> > > > > > > > > To post to this group, send email to [ats-l...@googlegroups.com](mailto:ats-l...@googlegroups.com).  
> > > > > > > > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > > > > > > > To view this discussion on the web visit  
> > > > > > > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com)  
> > > > > > > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > > > > > > > .
> > > > > > > 
> > > > > > > –  
> > > > > > > You received this message because you are subscribed to the Google  
> > > > > > > Groups “ats-lang-users” group.  
> > > > > > > To unsubscribe from this group and stop receiving emails from it, send  
> > > > > > > an email to [ats-lang...@googlegroups.com](mailto:ats-lang...@googlegroups.com) \<javascript:\>.  
> > > > > > > To post to this group, send email to [ats-l...@googlegroups.com](mailto:ats-l...@googlegroups.com)  
> > > > > > > \<javascript:\>.  
> > > > > > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > > > > > To view this discussion on the web visit  
> > > > > > > [https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com)  
> > > > > > > [https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/a59e0bc4-6148-4e0f-bab8-b2a7b2104bc5%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > > > > > .
> > 
> > –  
> > You received this message because you are subscribed to a topic in the  
> > Google Groups “ats-lang-users” group.  
> > To unsubscribe from this topic, visit  
> > [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe).  
> > To unsubscribe from this group and all its topics, send an email to  
> > [ats-lang...@googlegroups.com](mailto:ats-lang...@googlegroups.com) \<javascript:\>.  
> > To post to this group, send email to [ats-l...@googlegroups.com](mailto:ats-l...@googlegroups.com)  
> > \<javascript:\>.  
> > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > To view this discussion on the web visit  
> > [https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLqU6hSBn9mmjRpoy%3DXA1rZq8YMvzWYkMnfB7uuSu73AAA%40mail.gmail.com](https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLqU6hSBn9mmjRpoy%3DXA1rZq8YMvzWYkMnfB7uuSu73AAA%40mail.gmail.com)  
> > [https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLqU6hSBn9mmjRpoy%3DXA1rZq8YMvzWYkMnfB7uuSu73AAA%40mail.gmail.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLqU6hSBn9mmjRpoy%3DXA1rZq8YMvzWYkMnfB7uuSu73AAA%40mail.gmail.com?utm_medium=email&utm_source=footer)  
> > .

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [September 22, 2015, 2:22pm UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/15 "2015-09-22T14:22:12Z")

</div>

For a bit fun, I get the F-algebra code running:

> <https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats>

Well, it must be a bit crazy to program like this :)On Tuesday, September 22, 2015 at 9:01:38 AM UTC-4, gmhwxi wrote:

> Here is something that typechecks:
> 
> (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> //  
> infixr (-\>) -\>\>  
> //  
> typedef  
> -\>\> (a:type, b:type) = a - b  
> //  
> (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> 
> sortdef  
> ftype = type → type  
> typedef  
> Algebra (f:ftype, a:type) = f(a) -\>\> a
> 
> (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> //  
> extern  
> fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
> //  
> (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> 
> (\*  
> datatype  
> Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
> \*)
> 
> abstype  
> Fix(f:type → type)  
> extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))
> 
> (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> //  
> fun  
> cata{f:ftype}{a:type}  
> (alg: Algebra (f,a)): (Fix f -\>\> a) =  
> lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
> //  
> (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> 
> On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:
> 
> > Implementing F-Algebras in ATS, wondering what I’m doing wrong or where  
> > should I be looking? So far I have:
> > 
> > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > 
> > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > 
> > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f → a) =  
> > lam (f) =\> alg (map (cata alg) (f.invIso))
> > 
> > The last line does compile, says that map is out of scope. Where would I  
> > get it? Mind you, f is a Functor.

---

<div class="post-metadata">

**Author:** ![Aistis\_Raulinaitis](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Aistis\_Raulinaitis](https://discourse.ats-lang.org/u/Aistis_Raulinaitis)\
**Post date:** [September 26, 2015, 3:01am UTC](https://discourse.ats-lang.org/t/fuctorial-map/206/16 "2015-09-26T03:01:30Z")

</div>

The typechecker complains with:

patsopt -tc -d  
/home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats  
/home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
syntactic entity [s0taq] is needed.  
/home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
syntactic entity [si0de] is needed.  
/home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
639(line=50, offs=7) – 647(line=50, offs=15): error(parsing): the  
syntactic entity [s0exp] is needed.  
/home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
637(line=50, offs=5) – 638(line=50, offs=6): error(parsing): the keyword  
[=] is needed.  
/home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
629(line=49, offs=1) – 632(line=49, offs=4): error(parsing): the keyword  
‘}’ is needed.  
/home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
610(line=46, offs=17) – 613(line=46, offs=20): error(parsing): the  
syntactic entity [d0exp] is needed.  
/home/aistis/Projects/github/ATS-Postiats/doc/EXAMPLE/TESTATS/catamorph.dats:  
573(line=44, offs=1) – 582(line=44, offs=10): error(parsing): the token is  
discarded.  
exit(ATS): uncaught exception:  
\_2home\_2hwxi\_2research\_2Postiats\_2git\_2src\_2pats\_error\_2esats\_\_FatalErrorExn(1025)

Compilation exited abnormally with code 1 at Fri Sep 25 19:57:55On Thursday, September 24, 2015 at 7:30:29 PM UTC-7, gmhwxi wrote:

> I studied this cata-example a bit more.
> 
> As it stands now, this implementation is terribly slow.
> 
> I would like to suggest the following style of template-based  
> implementation of cata:
> 
> [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/TESTATS/catamorph.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/TESTATS/catamorph.dats)
> 
> I think it is quite involved to get the Haskell code (implementing  
> F-algebra) to run efficiently.  
> Cata(map) is clearly defined recursively and compiling it into efficient  
> code likely needs to have  
> deforestation optimization turned on.
> 
> The template-based implementation of cata in ATS does not create any  
> trees, and there is no ‘Fix’  
> clutter, either. All that is really needed for compiling the  
> implementation into efficient code is to inline  
> function calls aggressively.
> 
> On Wednesday, September 23, 2015 at 1:42:36 PM UTC-4, Aistis Raulinaitis wrote:
> 
> > The nice thing about F-algebras is that you can define fexpr\_eval  
> > non-recursively. It’s quite fast, a lot of performant libs in Haskell are  
> > written in terms of F-algebras. It’s especially good for languages that  
> > don’t handle recursion well, and a succinct way of defining ASTs.
> > 
> > Also, you can simplify fix\_unfold:
> > 
> > extern fun fix\_unfold {f:ftype} : Fix f → f (Fix f)  
> > implement fix\_unfold (Fx f) = f
> > 
> > On Tuesday, September 22, 2015 at 10:41:05 AM UTC-7, gmhwxi wrote:
> > 
> > > This one works on-line:
> > > 
> > > [http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas\_serve.php?mycode\_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra\_js.dats](http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas_serve.php?mycode_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/EXAMPLE/ATSLF/F-algebra_js.dats)
> > > 
> > > On Tuesday, September 22, 2015 at 1:01:51 PM UTC-4, Aistis Raulinaitis wrote:
> > > 
> > > > Beautiful! Thanks!
> > > > 
> > > > On Tue, Sep 22, 2015 at 7:22 AM, gmhwxi [gmh...@gmail.com](mailto:gmh...@gmail.com) wrote:
> > > > 
> > > > > For a bit fun, I get the F-algebra code running:
> > > > > 
> > > > > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLF/F-algebra.dats)
> > > > > 
> > > > > Well, it must be a bit crazy to program like this 🙂
> > > > > 
> > > > > On Tuesday, September 22, 2015 at 9:01:38 AM UTC-4, gmhwxi wrote:
> > > > > 
> > > > > > Here is something that typechecks:
> > > > > > 
> > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > //  
> > > > > > infixr (-\>) -\>\>  
> > > > > > //  
> > > > > > typedef  
> > > > > > -\>\> (a:type, b:type) = a - b  
> > > > > > //  
> > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > 
> > > > > > sortdef  
> > > > > > ftype = type → type  
> > > > > > typedef  
> > > > > > Algebra (f:ftype, a:type) = f(a) -\>\> a
> > > > > > 
> > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > //  
> > > > > > extern  
> > > > > > fun Map{f:ftype}{a,b:type} (a -\>\> b): f a -\>\> f b  
> > > > > > //  
> > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > 
> > > > > > (\*  
> > > > > > datatype  
> > > > > > Fix (f:type → type) = Iso of @{ invIso = f (Fix f) }  
> > > > > > \*)
> > > > > > 
> > > > > > abstype  
> > > > > > Fix(f:type → type)  
> > > > > > extern fun Fix\_unfold{f:ftype} : Fix(f) → f (Fix(f))
> > > > > > 
> > > > > > (\* \*\*\*\*\*\* \*\*\*\*\*\* _)  
> > > > > > //  
> > > > > > fun  
> > > > > > cata{f:ftype}{a:type}  
> > > > > > (alg: Algebra (f,a)): (Fix f -\>\> a) =  
> > > > > > lam (f: Fix(f)) =\> alg(Map(cata(alg))(Fix\_unfold(f)))  
> > > > > > //  
> > > > > > (_ \*\*\*\*\*\* \*\*\*\*\*\* \*)
> > > > > > 
> > > > > > On Tuesday, September 22, 2015 at 12:12:19 AM UTC-4, Aistis Raulinaitis wrote:
> > > > > > 
> > > > > > > Implementing F-Algebras in ATS, wondering what I’m doing wrong or  
> > > > > > > where should I be looking? So far I have:
> > > > > > > 
> > > > > > > datatype Algebra (f:t@ype → t@ype,a:t@ype) = Algebra of (f a)
> > > > > > > 
> > > > > > > datatype Fix (f:t@ype → t@ype) = Iso of @{ invIso = f (Fix f) }
> > > > > > > 
> > > > > > > fun cata {f:t@ype → t@ype}{a:t@ype} (alg:Algebra (f,a)): (Fix f →   
> > > > > > > a) = lam (f) =\> alg (map (cata alg) (f.invIso))
> > > > > > > 
> > > > > > > The last line does compile, says that map is out of scope. Where  
> > > > > > > would I get it? Mind you, f is a Functor.
> > > > > > 
> > > > > > –  
> > > > > > You received this message because you are subscribed to a topic in the  
> > > > > > Google Groups “ats-lang-users” group.  
> > > > > > To unsubscribe from this topic, visit  
> > > > > > [https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe](https://groups.google.com/d/topic/ats-lang-users/tfEnAR2vIOA/unsubscribe)  
> > > > > > .  
> > > > > > To unsubscribe from this group and all its topics, send an email to  
> > > > > > [ats-lang...@googlegroups.com](mailto:ats-lang...@googlegroups.com).  
> > > > > > To post to this group, send email to [ats-l...@googlegroups.com](mailto:ats-l...@googlegroups.com).  
> > > > > > Visit this group at [http://groups.google.com/group/ats-lang-users](http://groups.google.com/group/ats-lang-users).  
> > > > > > To view this discussion on the web visit  
> > > > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com)  
> > > > > > [https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/ats-lang-users/28a6f4f6-a0ee-4065-a5cb-b3bfa34a36c3%40googlegroups.com?utm_medium=email&utm_source=footer)  
> > > > > > .