Re: [Haskell-cafe] catamorphisms and attribute grammars
Hi Chris, thanks for insightful links. At the first glance, I think the main difference is that machines and iteratees process streams of data, while catamorphisms work on general recursive data structures. (I used count + sum in the example, which could lead to the impression that it's list oriented.) However, it seems to me that there is some connection between cata/anamorphisms and free (co)monads generated by a functor. I'm just guessing - perhaps using such a monad in a monadic pipe would lead to a similar result? BTW, while it seems that using existentials in by Cata data type is natural, I'd like to know if I could do it without them. If you have any ideas, please let me know. Best regards, Petr PS: Is there actually anything left that ekmett hasn't implemented? 2013/1/27 Chris Wong chrisyco+haskell-c...@gmail.com Hi Petr, Congratulations -- you've just implemented a Moore machine! [1] I posted something very much like this just last year [2]. It's a very common pattern in Haskell, forming the basis of coroutines and iteratees and many other things. Edward Kmett includes it in his machines package [3]. His variation, like mine, hides the state inside a closure, removing the need for existentials. pipes 2.0 contains one implemented as a free monad [4]. [1] http://en.wikipedia.org/wiki/Moore_machine [2] http://hackage.haskell.org/packages/archive/machines/0.2.3/doc/html/Data-Machine-Moore.html [3] http://www.haskell.org/pipermail/haskell-cafe/2012-May/101460.html [4] http://hackage.haskell.org/packages/archive/pipes/2.0.0/doc/html/Control-Pipe-Common.html Chris On Sun, Jan 27, 2013 at 11:03 AM, Petr P petr@gmail.com wrote: Dear Haskellers, I read some stuff about attribute grammars recently [1] and how UUAGC [2] can be used for code generation. I felt like this should be possible inside Haskell too so I did some experiments and I realized that indeed catamorphisms can be represented in such a way that they can be combined together and all run in a single pass over a data structure. In fact, they form an applicative functor. [1] http://www.haskell.org/haskellwiki/Attribute_grammar [2] Utrecht University Attribute Grammar Compiler To give an example, let's say we want to compute the average value of a binary tree. If we compute a sum first and then count the elements, the whole tree is retained in memory (and moreover, deforestation won't happen). So it's desirable to compute both values at once during a single pass: -- Count nodes in a tree. count' :: (Num i) = CataBase (BinTree a) i count' = ... -- Sums all nodes in a tree. sum' :: (Num n) = CataBase (BinTree n) n sum' = ... -- Computes the average value of a tree. avg' :: (Fractional b) = CataBase (BinTree b) b avg' = (/) $ sum' * count' Then we can compute the average in a single pass like runHylo avg' treeAnamorphism seed My experiments together with the example are available at https://github.com/ppetr/recursion-attributes I wonder, is there an existing library that expresses this idea? Best regards, Petr Pudlak ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] catamorphisms and attribute grammars
Roman, this is interesting. Is this arrow generalization in some library
already? And does it have a name?
Best regards,
Petr Pudlak
2013/1/27 Roman Cheplyaka r...@ro-che.info
* Petr P petr@gmail.com [2013-01-26 23:03:51+0100]
Dear Haskellers,
I read some stuff about attribute grammars recently [1] and how UUAGC [2]
can be used for code generation. I felt like this should be possible
inside
Haskell too so I did some experiments and I realized that indeed
catamorphisms can be represented in such a way that they can be combined
together and all run in a single pass over a data structure. In fact,
they
form an applicative functor.
...
My experiments together with the example are available at https://github
.com/ppetr/recursion-attributes
Very nice! This can be generalized to arbitrary arrows:
{-# LANGUAGE ExistentialQuantification #-}
import Prelude hiding (id)
import Control.Arrow
import Control.Applicative
import Control.Category
data F from to b c = forall d . F (from b d) (to d c)
instance (Arrow from, Arrow to) = Functor (F from to b) where
fmap f x = pure f * x
instance (Arrow from, Arrow to) = Applicative (F from to b) where
pure x = F (arr $ const x) id
F from1 to1 * F from2 to2 =
F (from1 from2) (to1 *** to2 arr (uncurry id))
Now your construction is a special case where 'from' is the category of
f-algebras and 'to' is the usual (-) category.
I wonder what's a categorical interpretation of F itself.
Roman
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Where did the Cabal manual go?
I'm not able to access the cabal manual today: links to my local copy and links to the copy at haskell.org result in a 404. I'm running the Haskell Platform, 2012.4.0.0, 64-bit, OS X 10.8.2. On my first attempt this morning, I loaded file:///Library/Haskell/doc/start.html in my browser and clicked on the Cabal link. The browser can't find file:///Library/Haskell/doc/ghc-doc/Cabal/index.html, and indeed the directory /Library/Haskell/doc/ghc-doc/Cabal doesn't exist. Ok, I think, so my local copy's gotten corrupted. One sudo /Library/Haskell/bin/uninstall-hs --remove thru 7.4.2 and reinstall later, I try again; no change. I also can't find any docs by doing find /Library/Haskell -iname \*cabal\* find /Library/Frameworks/GHC.framework -iname \*cabal\* either. I also get a 404 when I click on the Cabal link from http://lambda.haskell.org/platform/doc/current/start.html. I can probably recover a copy from system backups, but what's going on? Richard ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to store Fixed data type in the database with persistent ?
On Jan 27, 2013 8:46 AM, alexander.vershi...@gmail.com wrote:
Sat, Jan 26, 2013 at 12:21:02PM +0600, s9gf4...@gmail.com wrote
According to the documentation, SQLite stores whatever you give it,
paying very little heed to the declared type. If you get SQLite to
*compare* two numbers, it will at that point *convert* them to doubles
in order to carry out the comparison. This is quite separate from the
question of what it can store.
CREATE TABLE t1(val);
sqlite insert into t1 values ('24.24242424')
... ;
sqlite insert into t1 values ('24.24242423')
... ;
sqlite select * from t1 order by val;
24.24242423
24.24242424
sqlite select * from t1 order by val desc;
24.24242424
24.24242423
sqlite select sum(val) from t1;
48.48484847
it seems Sqlite can work with arbitrary percission data, very good !
Persistent must have ability to store Fixed.
It's not correct. SQLlite stores any value, but it will use arithmetic
operations only with double presicion:
sqlite select val from t1;
1
0.01
0.0001
0.01
0.0001
0.01
0.0001
0.01
0.0001
0.01
sqlite select sum(val) from t1;
1.0101010101
as you see it has 14 degree.
Let's check another well known floating point problem:
sqlilte create table t2 ('val')
sqlite insert into t2 values ('0.7');
sqlite update t2 set val = 11*val-7;
t2 should remain a const
sqlite update t2 set val = 11*val-7; -- 4 times
sqlite select val from t2;
0.6989597
sqlite update t2 set val = 11*val-7; -- 10 times mote
sqlite select val from t2;
0.430171514341321
As you see you have errors. So SQLlite doesn't support arbitrary
presision values.
As for me Persistent should at least support a Money type and use
correct backend-specific type for them, either a native for big integer.
Let me clarify a bit:
1. Persistent will currently allow you to create a `Money` datatype which
internally stores as an integer.
2. What Persistent currently lacks is a PersistValue constructor for
arbitrary-precision values. As a result, during marshaling, some data will
be lost when converting from NUMERIC to Double.
3. The upcoming change we're discussing for Persistent would just be to add
such a constructor. We could theoretically provide some extra PersistField
instances as well, but that's not really what's being discussed.
HTH,
Michael
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Where did the Cabal manual go?
Do you mean the Cabal User Guide? http://www.haskell.org/cabal/users-guide/ On Sun, Jan 27, 2013 at 1:07 PM, Richard Cobbe co...@ccs.neu.edu wrote: I'm not able to access the cabal manual today: links to my local copy and links to the copy at haskell.org result in a 404. I'm running the Haskell Platform, 2012.4.0.0, 64-bit, OS X 10.8.2. On my first attempt this morning, I loaded file:///Library/Haskell/doc/start.html in my browser and clicked on the Cabal link. The browser can't find file:///Library/Haskell/doc/ghc-doc/Cabal/index.html, and indeed the directory /Library/Haskell/doc/ghc-doc/Cabal doesn't exist. Ok, I think, so my local copy's gotten corrupted. One sudo /Library/Haskell/bin/uninstall-hs --remove thru 7.4.2 and reinstall later, I try again; no change. I also can't find any docs by doing find /Library/Haskell -iname \*cabal\* find /Library/Frameworks/GHC.framework -iname \*cabal\* either. I also get a 404 when I click on the Cabal link from http://lambda.haskell.org/platform/doc/current/start.html. I can probably recover a copy from system backups, but what's going on? Richard ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Where did the Cabal manual go?
On Sun, Jan 27, 2013 at 03:47:38PM -0200, Felipe Almeida Lessa wrote: Do you mean the Cabal User Guide? http://www.haskell.org/cabal/users-guide/ Yes, that's it, and I'm in the process of downloading a copy now (so I can work without a WiFi connection). I'm still curious about why there's a broken link on http://lambda.haskell.org/platform/doc/current/start.html, and what on earth I did to delete the copy of the user's guide that used to be on my hard drive as part of the Haskell Platform installation (or, worse, what was silently done on my behalf). It's possible I missed a notification that this was happening, but I certainly don't remember seeing anything to that effect. Richard ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Where did the Cabal manual go?
On Sun, Jan 27, 2013 at 01:48:06PM -0500, Richard Cobbe wrote: On Sun, Jan 27, 2013 at 03:47:38PM -0200, Felipe Almeida Lessa wrote: Do you mean the Cabal User Guide? http://www.haskell.org/cabal/users-guide/ Yes, that's it, and I'm in the process of downloading a copy now (so I can work without a WiFi connection). By the way, if the Cabal users guide is no longer to be packaged with the Haskell Platform, can I suggest adding a link to http://www.haskell.org/cabal that would allow folks to download a tgz with the HTML docs, much as is provided for Happy and Alex? As it is, one has to download 4 html files and a css file and hope that's everything. Richard ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] catamorphisms and attribute grammars
You have applied the so-called banana-split theorem, as described e.g. in
http://www.cs.ox.ac.uk/jeremy.gibbons/publications/acmmpc-calcfp.pdf
Indeed you are right in noticing the correspondence between AG's and
catamorphims; actually I see AG's as a domain specific language for
constructing algebras.
Since we believe in embedded domain specific languages we have developed a
library for constructing attribute grammars in Haskell, which is described in
our ICFP paper:
@inproceedings{1596586,
Address = {New York, NY, USA},
Author = {Viera, Marcos and Swierstra, S. Doaitse and Swierstra,
Wouter},
Booktitle = {ICFP '09: Proceedings of the 14th ACM SIGPLAN
international conference on Functional programming},
Date-Added = {2009-10-05 22:06:26 +0200},
Date-Modified = {2009-10-05 22:06:26 +0200},
Doi = {http://doi.acm.org/10.1145/1596550.1596586},
Isbn = {978-1-60558-332-7},
Location = {Edinburgh, Scotland},
Pages = {245--256},
Publisher = {ACM},
Title = {Attribute grammars fly first-class: how to do aspect oriented
programming in Haskell},
Year = {2009}}
where you will find the problem you are solving done using the library.
On March 8 2013 Marcos Viera hopes to defend his Ph.D. thesis at Utrecht
University. His thesis contains the progress we have made in this area in
recent years. You can find it at the bottom op the page; amongst others you can
use the UUAGC nowadays to generate this code form uuagc input.
http://www.cs.uu.nl/wiki/bin/view/Center/PhDs
Doaitse Swierstra
On Jan 26, 2013, at 23:03 , Petr P petr@gmail.com wrote:
Dear Haskellers,
I read some stuff about attribute grammars recently [1] and how UUAGC [2] can
be used for code generation. I felt like this should be possible inside
Haskell too so I did some experiments and I realized that indeed
catamorphisms can be represented in such a way that they can be combined
together and all run in a single pass over a data structure. In fact, they
form an applicative functor.
[1] http://www.haskell.org/haskellwiki/Attribute_grammar
[2] Utrecht University Attribute Grammar Compiler
To give an example, let's say we want to compute the average value of a
binary tree. If we compute a sum first and then count the elements, the whole
tree is retained in memory (and moreover, deforestation won't happen). So
it's desirable to compute both values at once during a single pass:
-- Count nodes in a tree.
count' :: (Num i) = CataBase (BinTree a) i
count' = ...
-- Sums all nodes in a tree.
sum' :: (Num n) = CataBase (BinTree n) n
sum' = ...
-- Computes the average value of a tree.
avg' :: (Fractional b) = CataBase (BinTree b) b
avg' = (/) $ sum' * count'
Then we can compute the average in a single pass like
runHylo avg' treeAnamorphism seed
My experiments together with the example are available at
https://github.com/ppetr/recursion-attributes
I wonder, is there an existing library that expresses this idea?
Best regards,
Petr Pudlak
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] GHC.Generics and newtypes
Hi, Is it possible to generate different instances for newtypes and datatypes using GHC.Generics? Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC.Generics and newtypes
Hi Roman, Yes, the automatic derivation of Generic instances does not see through newtypes. Cheers, Pedro On Sun, Jan 27, 2013 at 8:17 PM, Roman Cheplyaka r...@ro-che.info wrote: Hi, Is it possible to generate different instances for newtypes and datatypes using GHC.Generics? Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC.Generics and newtypes
Sorry, I wasn't clear. What I want is somehow to find out whether the type under consideration is declared using data or newtype. Is it possible? Roman * José Pedro Magalhães j...@cs.uu.nl [2013-01-27 20:29:52+] Hi Roman, Yes, the automatic derivation of Generic instances does not see through newtypes. Cheers, Pedro On Sun, Jan 27, 2013 at 8:17 PM, Roman Cheplyaka r...@ro-che.info wrote: Hi, Is it possible to generate different instances for newtypes and datatypes using GHC.Generics? Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC.Generics and newtypes
Ah, no. But that would be easy to add to the Datatype classhttp://hackage.haskell.org/packages/archive/base/4.6.0.0/doc/html/GHC-Generics.html#g:3, I think. Perhaps open a feature request? Cheers, Pedro On Sun, Jan 27, 2013 at 8:34 PM, Roman Cheplyaka r...@ro-che.info wrote: Sorry, I wasn't clear. What I want is somehow to find out whether the type under consideration is declared using data or newtype. Is it possible? Roman * José Pedro Magalhães j...@cs.uu.nl [2013-01-27 20:29:52+] Hi Roman, Yes, the automatic derivation of Generic instances does not see through newtypes. Cheers, Pedro On Sun, Jan 27, 2013 at 8:17 PM, Roman Cheplyaka r...@ro-che.info wrote: Hi, Is it possible to generate different instances for newtypes and datatypes using GHC.Generics? Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC.Generics and newtypes
Sure. Should it go to the GHC bug tracker? Roman * José Pedro Magalhães j...@cs.uu.nl [2013-01-27 20:36:54+] Ah, no. But that would be easy to add to the Datatype classhttp://hackage.haskell.org/packages/archive/base/4.6.0.0/doc/html/GHC-Generics.html#g:3, I think. Perhaps open a feature request? Cheers, Pedro On Sun, Jan 27, 2013 at 8:34 PM, Roman Cheplyaka r...@ro-che.info wrote: Sorry, I wasn't clear. What I want is somehow to find out whether the type under consideration is declared using data or newtype. Is it possible? Roman * José Pedro Magalhães j...@cs.uu.nl [2013-01-27 20:29:52+] Hi Roman, Yes, the automatic derivation of Generic instances does not see through newtypes. Cheers, Pedro On Sun, Jan 27, 2013 at 8:17 PM, Roman Cheplyaka r...@ro-che.info wrote: Hi, Is it possible to generate different instances for newtypes and datatypes using GHC.Generics? Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suggestiong for inter-thread communication
Hi Eric, In a previous project, I chose vty over ncurses: - you can write your own event loop, and hence handle different event sources. - more liberal license (BSD3 versus GPL) Tim On 26/01/13 19:24, Erik de Castro Lopo wrote: Hi all, I am in the process of writing a Haskell program consisting of two threads, one for performing a calculation and one for an Ncurses UI (haskell-ncurses). The calculation thread needs to feed a stream of numbers back to the UI thread (about 1 value per second) and the UI needs to take input from the user and will pass parameter changes to the calculation thread using an IORef and atomicModifyIORef. However, I'm not sure how to hande the UI thread. The UI thread would normally wait for Ncurses input using getEvent, but I need advice on how to the the data from the calculation thread. Any advice or things to try? Cheers, Erik ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
