Re: [Haskell-cafe] Free theorems for dependent types?

[Eugene Kirpichov]

Thanks, at least the title looks like exactly what I've been looking
for, however I cannot quickly appreciate the notation-heavy contents:
I definitely will as soon as possible.

2009/5/20 Masahiro Sakai :
> From: Eugene Kirpichov 
> Date: Sun, 17 May 2009 23:10:12 +0400
>
>> Is there any research on applying free theorems / parametricity to
>> type systems more complex than System F; namely, Fomega, or calculus
>> of constructions and alike?
>
> You may be interested in this:
> "The Theory of Parametricity in Lambda Cube" by Takeuti Izumi
> http://www.m.is.sci.toho-u.ac.jp/~takeuti/abs-e.html#cube
>
> -- Masahiro Sakai
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Free theorems for dependent types?

[Eugene Kirpichov]

Thanks for the thorough response.

I've found Barras&Bernardo's work (at least, slides) about ICC*, I'll
have a look at it.
Could you provide with names of works by Altenkirch/Morris/Oury/you?
The unordered pair example was especially interesting, since I am
somewhat concerned with which operations do not break parametricity
for *unordered sets* (as opposed to lists) - turns out, not too many.


2009/5/18 Conor McBride :
> Hi
>
> Questions of parametricity in dependent types are made more
> complex by the way in which the "Pi-type"
>
>  (x : S) -> T
>
> corresponds to universal quantification. It's good to think
> of this type as a very large product, tupling up individual
> T's for each possible x you can distinguish by observation.
> "For all x" here means "For each individual x".
>
> By contrast, your typical universally quantified type
>
>  forall x. t
>
> gives you fantastic guarantees of ignorance about x! It's
> really a kind of intersection. "For all x" here means
> "For a minimally understood x" --- your program should work
> even when x is replaced by a cardboard cutout rather than
> an actual whatever-it-is, and this guarantees the
> uniformity of operation which free theorems exploit.
> I'm reminded of the Douglas Adams line "We demand rigidly
> defined areas of doubt and uncertainty.".
>
> In the dependent case, how much uniformity you get depends
> on what observations are permitted on the domain. So what's
> needed, to get more theorems out, is a richer language of
> controlled ignorance. There are useful developments:
>
>  (1) Barras and Bernardo have been working on a dependent
>    type system which has both of the above foralls, but
>    distinguishes them. As you would hope, the uniform
>    forall, its lambda, and application get erased between
>    typechecking and execution. We should be hopeful for
>    parametricity results as a consequence.
>
>  (2) Altenkirch, Morris, Oury, and I have found a way
>    (two, in fact, and there's the rub) to deliver
>    quotient structures, which should allow us to specify
>    more precisely which observations are available on a
>    given set. Hopefully, this will facilitate parametric
>    reasoning --- if you can only test this, you're bound
>    to respect that, etc. My favourite example is the
>    recursion principle on *unordered* pairs of numbers
>    (N*N/2).
>
>    uRec :
>    (P : N*N/2 -> Set) ->
>    ((y : N) -> P (Zero, y)) ->
>    ((xy : N*N/2) -> P xy -> P (map Suc xy)) ->
>    (xy : N*N/2) -> P xy
>
>    Given an unordered pair of natural numbers, either
>    one is Zero or both are Suc, right? You can define
>    some of our favourite operators this way.
>
>    add  = uRec (\ _ -> N) (\ y -> y) (\ _ -> Suc . Suc)
>    max  = uRec (\ _ -> N) (\ y -> y) (\ _ -> Suc)
>    min  = uRec (\ _ -> N) (\ y -> y) (\ _ -> id)
>    (==) = uRec (\ _ -> Bool) isZero (\ _ -> id)
>
>    I leave multiplication as an exercise.
>
>    The fact that these operators are commutative is
>    baked into their type.
>
> To sum up, the fact that dependent types are good at
> reflection makes them bad at parametricity, but there's
> plenty of work in progress aimed at the kind of information
> hiding which parametricity can then exploit.
>
> There are good reasons to be optimistic here.
>
> All the best
>
> Conor
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Tree traversal / stack overflow

[Matthew Eastman]

Hi,

I've been writing some code to calculate the stretch factor of a tree  
of points. What it means is that for every node in a tree (lets call  
it 'pivot'), I have to traverse the same tree (lets call each node  
'current') and sum d_t(pivot, current) / d(pivot, current) for each  
node, where d_t is the tree path distance between two nodes and d is  
the Euclidean distance.


What I've been doing is traversing the tree, pivoting up each node  
into the root position, and calculating the stretch factor for each  
new tree.


ex.  +===+ +===+  +===+
 | 1 | | 2 |  | 3 |
 +===+ .---+===+. +===+
/ /|   | \ \
   +---+ +---+  +---+  +---+  +---+ +---+
   | 2 | --->| 3 |  | 4 |  | 5 |  | 1 | --->| 2  
|   etc.

  .+---+.+---+  +---+  +---+  +---+.+---+.
 /   |   \/   |   \
+---+  +---+  +---+  +---+  +---+   
+---+
| 3 |  | 4 |  | 5 |  | 4 |  | 5 |   
| 1 |
+---+  +---+  +---+  +---+  +---+   
+---+



The code I have right now works great on point sets of size ~10,000,  
but when I go up much higher things start to go wrong. I start hitting  
stack overflows, so I increased the stack size. For ~100,000 points  
though, running the code with +RTS -sstderr -K128m it chugged along  
for over an hour and then died with a stack overflow. The stats said  
it spent 50 seconds MUT time and 5300 seconds (almost 90 minutes!) GC  
time, which seems odd.


The performance has been really good for lower numbers of points, but  
the professor I'm working for wants to handle over a million points  
later on. I've only been writing Haskell for a year, and I'm not quite  
sure how to rewrite this so that it won't blow the stack, since I'm  
pretty sure this kind of tree traversal can't be done with tail calls  
(I would love to proved wrong, though!). Any help would be appreciated.


Thanks,
Matt

module ASF (
averageStretchFactor
) where

import Data.Tree
import Data.Foldable (foldr')

type Point = (Double,Double)

square :: Double -> Double
square x = x * x

dist :: Point -> Point -> Double
dist (x1,y1) (x2,y2) = sqrt (square (x2 - x1) + square (y2 - y1))

add :: Tree a -> Tree a -> Tree a
add (Node p sts) t = Node p (t:sts)

-- Calculate the average stretch factor of a tree of size n. It's the  
sum of
-- the average stretch factor of each node in the tree, divided by n  
choose 2

-- (the number of possible pairs of points in in a tree of size n)
averageStretchFactor :: Tree Point -> Double -> Double
averageStretchFactor tree n = stretchRotations tree / (n * (n - 1) / 2)

-- Calculate the stretch factor of a tree.
-- The stretch of two points is the tree path distance between the two  
points
-- divided by the euclidean distance between the two points. The  
stretch factor
-- of a tree is the sum of the stretches between the root and every  
other node

-- in the tree.
stretchFactor :: Tree Point -> Double
stretchFactor (Node point sts) = stretch 0 point sts
  where
stretch _ _ [] = 0
stretch d p ((Node p' sts'):ts) = pd / ed + stretch pd p' sts' +  
stretch d p ts

  where
pd = d + dist p p' -- path distance
ed = dist point p' -- euclidean distance

-- Calculate the stretch factor of every point by pulling up each node  
in the
-- tree to the root position. Note that the overall structure of the  
tree
-- doesn't change, we're essentially just traversing the tree and  
calculating

-- the stretch factor of each node by pretending we're at the root.
stretchRotations :: Tree Point -> Double
stretchRotations tree = rotate tree []
  where
rotate tree@(Node p sts) path = stretchFactor (foldr' add tree  
path) + pivot [] sts path p

pivot _  [] __ = 0
pivot ls (r:rs) path p = rotate r (Node p (ls ++ rs) : path) +  
pivot (r:ls) rs path p



./main 1 +RTS -sstderr -K128m
ASF = 22.441
   1,298,891,896 bytes allocated in the heap
  20,191,904 bytes copied during GC
   3,107,116 bytes maximum residency (7 sample(s))
  47,480 bytes maximum slop
   8 MB total memory in use (0 MB lost due to  
fragmentation)


  Generation 0:  2471 collections, 0 parallel,  0.06s,  0.07s  
elapsed
  Generation 1: 7 collections, 0 parallel,  0.03s,  0.03s  
elapsed


  INIT  time0.00s  (  0.00s elapsed)
  MUT   time   13.05s  ( 13.18s elapsed)
  GCtime0.09s  (  0.11s elapsed)
  EXIT  time0.00s  (  0.00s elapsed)
  Total time   13.14s  ( 13.29s elapsed)

  %GC time   0.7%  (0.8% elapsed)

  Alloc rate99,506,082 bytes per MUT second

  Productivity  99.3% of total user, 98.2% of total elapsed


./main 10 +RTS -sstderr -K128m

Re: [Haskell-cafe] Performance Problem with Typeable

[Michael D. Adams]

I've opened a ticket for this
(http://hackage.haskell.org/trac/ghc/ticket/3245), but someone else
will have to do the investigation into the problem.

Michael D. Adams

On Thu, May 14, 2009 at 10:59 AM, Simon Peyton-Jones
 wrote:
> Interesting.  Would anyone care to make a Trac ticket for this (with "perf 
> bug" as  the ticket kind), and (if at all possible) do some investigation to 
> see what is going on?
>
> Many thanks
>
> Simon
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] How i use GHC.Word.Word8 wit Int ?

[Lee Duhem]

2009/5/20 Bernie Pope :
> Oh right. I didn't see your proposal (did it get sent to the list?).

Yes, I just push the Replay button, not the

> Sorry for the confusion.

It's my fault, sorry.

lee
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] How i use GHC.Word.Word8 wit Int ?

[Johannes Laire]

On Wed, May 20, 2009 at 3:40 AM, z_a...@163.com  wrote:
> Hi, friends
>
> rollDice :: Word8 -> IO Word8
> rollDice n = do
>   bracket (openFile "/dev/random" ReadMode) (hClose)
>       (\hd -> do v <-  fmap B.unpack (B.hGet hd 1)
>                  let v1 =  Data.List.head v
>                  return $ (v1 `mod` n) + 1)
> .
> blueIdx <- rollDice $ length [1..33]
>
> Couldn't match expected type `Word8' against inferred type `Int'
>   In the second argument of `($)', namely `length yesBlue
>
> I know "length [1..33]" is Int not Word8, but Word8 is enough here.
> Sincerely!

Word8 is an instance of Num, so you could use
Data.List.genericLength, which has the type:

genericLength :: Num i => [b] -> i

http://haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#26

-- 
Johannes Laire
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] How to use Data.ByteString ?

[Brandon S. Allbery KF8NH]

On May 19, 2009, at 10:20 , Chaddaï Fouché wrote:

On Tue, May 19, 2009 at 8:46 AM, Brandon S. Allbery KF8NH
 wrote:

On May 19, 2009, at 01:42 , Jason Dagit wrote:

I've often seen this bit of scary code in VB:
Dim i as Integer = 5
If i = "5" Then
 ' Do something, because 5 = "5"
End If


Sure, that works in Perl too.


That's because in numeric context Perl convert strings into numbers,
so even 5 == "5 coffees" would be true... But 5 eq "5 coffees"
wouldn't since eq force a string context and 5 is converted to "5"


If you use == instead of eq then it will emit a warning and then find  
them equal.  This is something of a common logic error in Perl.


--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com
system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu
electrical and computer engineering, carnegie mellon universityKF8NH




PGP.sig
Description: This is a digitally signed message part
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] How i use GHC.Word.Word8 wit Int ?

[Bernie Pope]

2009/5/20 z_a...@163.com :
> Hi, friends
>
> rollDice :: Word8 -> IO Word8
> rollDice n = do
>   bracket (openFile "/dev/random" ReadMode) (hClose)
>       (\hd -> do v <-  fmap B.unpack (B.hGet hd 1)
>                  let v1 =  Data.List.head v
>                  return $ (v1 `mod` n) + 1)
> .
> blueIdx <- rollDice $ length [1..33]
>
> Couldn't match expected type `Word8' against inferred type `Int'
>   In the second argument of `($)', namely `length yesBlue
>
> I know "length [1..33]" is Int not Word8, but Word8 is enough here.
> Sincerely!

You can use fromIntegral to convert Integral types to other numeric types:

   fromIntegral :: (Integral a, Num b) => a -> b

Prelude Data.Word> (fromIntegral (3 :: Int)) :: Word8
3

Watch out for overflow.

Cheers,
Bernie.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Haskell progr ammers in São Carlos - SP - Brazil?

[Diego Souza]

Not exactly São Carlos: São Paulo - SP.

On Tue, May 19, 2009 at 09:28:55PM -0300, Maurí­cio wrote:
> Anybody else around here?
>
> Best,
> Maurício
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

-- 
~dsouza
yahoo!im: paravinicius
gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B  9ECE F88E 067F E891 651E
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] How i use GHC.Word.Word8 wit Int ?

[Felipe Lessa]

On Wed, May 20, 2009 at 08:40:15AM +0800, z_a...@163.com wrote:
> I know "length [1..33]" is Int not Word8, but Word8 is enough here.

Just saying '33' is enough here. :)

--
Felipe.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] How i use GHC.Word.Word8 wit Int ?

[z_a...@163.com]

Hi, friends

rollDice :: Word8 -> IO Word8
rollDice n = do
   bracket (openFile "/dev/random" ReadMode) (hClose)
   (\hd -> do v <-  fmap B.unpack (B.hGet hd 1)
  let v1 =  Data.List.head v
  return $ (v1 `mod` n) + 1)
.
blueIdx <- rollDice $ length [1..33]

Couldn't match expected type `Word8' against inferred type `Int'
   In the second argument of `($)', namely `length yesBlue

I know "length [1..33]" is Int not Word8, but Word8 is enough here.  


Sincerely!

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Haskell programmers in São Carlos - SP - Brazil?

[Maurí­cio]

Anybody else around here?

Best,
Maurício

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] showing a user defined type

[michael rice]

Hi Ryan,

I'm afraid you've lost me. Maybe if you showed how this would be used in ML I 
would get the picture.

Michael

--- On Tue, 5/19/09, Ryan Ingram  wrote:

From: Ryan Ingram 
Subject: Re: [Haskell-cafe] showing a user defined type
To: "michael rice" 
Cc: "Brandon S. Allbery KF8NH" , haskell-cafe@haskell.org
Date: Tuesday, May 19, 2009, 2:40 PM

On Tue, May 19, 2009 at 7:07 AM, michael rice  wrote:
> A little further along in "The Little MLer" the ints function is replaced by
> other functions like primes and fibs, which also return Links:
>
> fun primes(n)
>   = if is_prime(n+1)
>  then Link(n+1,primes)
>  else primes(n+1)
>
> fun fibs(n)(m)
>   = Link(n+m,fibs(m))
>
> which are passed to chain_item:
>
> fun chain_item(n,Link(i,f))
>   = if eq_int(n,1)
>   then i
>   else chain_item(n-1,f(i))
>
> which can be called to request the nth (12th) prime number beginning at 1.
>
> - chain_item(12,primes(1));
> GC #0.0.0.1.3.61:   (1 ms)
> val it = 37 : int
> -
>
> So I guess the answer to your question about whether the function is ever
> called with a different value may be, yes.

Actually, it's not calling it with another value; notice that
chain_item calls f(i), with i coming directly from the chain.
Consider this alternate definition:
(I'm not sure the syntax is exactly right, but you get the idea)

datatype chain =
  Link of (int * ( unit -> chain ))

fun intsFrom(n) = fun unit => (n, intsFrom (n+1))
fun ints(n) = intsFrom n ()

Now you *can't* call the function embedded in the link with another value.

fun chain_item(n,Link(i,f))
  = if eq_int(n,1)
  then i
  else chain_item(n-1,f unit)

And this type for "chain" is almost the same as [Int] in Haskell, due
to laziness.

  -- ryan



  ___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Free theorems for dependent types?

[Masahiro Sakai]

From: Eugene Kirpichov 
Date: Sun, 17 May 2009 23:10:12 +0400

> Is there any research on applying free theorems / parametricity to
> type systems more complex than System F; namely, Fomega, or calculus
> of constructions and alike?

You may be interested in this:
"The Theory of Parametricity in Lambda Cube" by Takeuti Izumi
http://www.m.is.sci.toho-u.ac.jp/~takeuti/abs-e.html#cube

-- Masahiro Sakai
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] fast Eucl. dist. - Haskell vs C

[Patrick Perry]

Hi Kenneth,

I wrote a benchmark similar to yours using the haskell blas library I  
wrote (latest version is on github at http://github.com/patperry/blas/tree/master 
, an older version is on hackage).


The pure Haskell implementation is not very good, and the problem  
seems to be repeated boxing/unboxing of doubles.  It may be possible  
to avoid this by writing a custom "fold" function for Vectors, but I  
haven't tried it.  Using a vectorized subtraction function along with  
the BLAS1 "dnrm2" function, I was able to get performance about  
2.8-5.4x worse than C.  This isn't great, but it's not terrible,  
either.  I didn't have the performance problems you ran in to using  
the FFI.  My benchmark includes:


distVectors1: a native implementation using foldl' and zipWith
distVectors2: a vectorize implementation, defined as @distVectors2 x y  
= norm2 (x-y)@

distVectors3: a custom loop in haskell
distVectors4: an FFI call to C

All 4 functions use the "Vector" type, provided by the "blas" package.

I compiled with "-O -fexcess-preceision" and ran timings for vectors  
of size 10, 100, and 1000.  Here are the results:


Macintosh-62:~/Code/blas/examples (euclidean)$ ./Euclidean 10
n: 10
* distVectors1: .
  1.366ns per iteration / 732029.06 per second.
* distVectors2: .
  1.286ns per iteration / 34.02 per second.
* distVectors3: ..
  0.950ns per iteration / 1052847.93 per second.
* distVectors4: ...
  0.452ns per iteration / 2213752.56 per second.
Macintosh-62:~/Code/blas/examples (euclidean)$ ./Euclidean 100
n: 100
* distVectors1: ..
  12.496ns per iteration / 80025.79 per second.
* distVectors2: 
  2.149ns per iteration / 465311.61 per second.
* distVectors3: ..
  8.728ns per iteration / 114572.53 per second.
* distVectors4: ..
  0.597ns per iteration / 1675765.65 per second.
Macintosh-62:~/Code/blas/examples (euclidean)$ ./Euclidean 1000
n: 1000
* distVectors1: ..
  125.920ns per iteration / 7941.52 per second.
* distVectors2: ..
  10.677ns per iteration / 93661.99 per second.
* distVectors3: ...
  85.533ns per iteration / 11691.42 per second.
* distVectors4: 
  1.962ns per iteration / 509668.17 per second.

The "distVectors2" function is computing the norm in a more  
numerically-stable way.  It is also allocating a temporary array to  
store x-y.


I haven't looked over your benchmarking code too thoroughly, but parts  
of it seem suspect to me.  Namely, you are using "mapM" instead of  
"mapM_".  Also, it seems like you are including GC times in your  
benchmarks.


Attached is my code.  You will need the latest "blas" from github to  
compile it.  You also might want to look into hmatrix.  I have very  
little time for haskell code right now (I'm trying to finish my Ph.D.  
in the next month).  This summer I plan to work more on this stuff,  
and I'll probably make a release in July.



Patrick



Euclidean.hs
Description: Binary data





dist.c
Description: Binary data


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] ANN: atom 0.0.4

[Tom Hawkins]

This new version of atom adds an array datatype (A a), which has
helped us shrink and speed up the embedded code in our application.
Enjoy!

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/atom

-Tom
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Gtk2Hs + Sourceview on Windows

[mwinter]

Hi,

I have ghc 6.10.1 and gtk2hs 0.10.0 installed on my windows vista
computer. Both were installed using the installer on the webpages.
I am able to use gtk, glade etc but not sourceview or cairo. If I
compile the examples in the gtk2hs example folder, I get "not in 
scope" error messages for functions from those library components.
In a forum I found that those have to be enabled using 
./configure --enable-sourceview
(similar for cairo). But my windows installation does not seem to
have a script configure or a similar program. What am I supposed 
to do?

Thanks,
Michael

--
Michael WinterBrock University
Associate Professor500 Glenridge Avenue
Department of Computer Science  St. Catharine, ON, L2S 3 A1
Phone: +1 905 688 5550 ext 3355  Fax: +1 905 688 3255
-
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: Question about IO, interact functions,

[Ertugrul Soeylemez]

David Leimbach  wrote:

> main = interact (unlines . lines)
> This *appears* to somewhat reliably get me functionality that looks like
> take a line of input, and print it out.
>
> Is this behavior something I can rely on working?
>
> I like the idea that lines can pull lines lazily from "getContents"
> which lazily consume the input.  But I'm concerned that relying on a
> pure function like "unlines . lines" to sequence IO is a bit too
> implicit in nature.

As Jason pointed out, you're relying on getContents.  Your little
function composition "unlines . lines" will do nothing at all in most
cases, although in some configurations it may replace line feed
representations.  What you're really relying on is the buffering method
used by 'stdin' and 'stdout'.  If you want to make sure, use the
following:

  import System.IO

  main :: IO ()
  main = do
mapM_ (`hSetBuffering` LineBuffering) [stdin, stdout]
iterate f


> I really like the idea of doing things through functions like Interact
> in that they appear to allow me to keep most of my code pure, but if I
> can't get the IO sequencing I want to be guaranteed to work, I suppose
> I'll have to dive back into "imperative IO" land that I get from the
> IO Monad.
>
> Should I feel guilty for doing so?  :-)

Not always.  Especially when writing concurrent code for things like
servers, I usually write highly imperative code, using functional
constructs where appropriate.  Being a functional language of course
makes Haskell much more powerful and expressive, but it has lots of more
advantages like an amazing concurrency system. =)

Note:  'Iterate' would be a type, a class or a module.  Functions (and
type variables) _must_ be written in lower-case in Haskell.


Greets,
Ertugrul.


-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] showing a user defined type

[Ryan Ingram]

On Tue, May 19, 2009 at 7:07 AM, michael rice  wrote:
> A little further along in "The Little MLer" the ints function is replaced by
> other functions like primes and fibs, which also return Links:
>
> fun primes(n)
>   = if is_prime(n+1)
>  then Link(n+1,primes)
>  else primes(n+1)
>
> fun fibs(n)(m)
>   = Link(n+m,fibs(m))
>
> which are passed to chain_item:
>
> fun chain_item(n,Link(i,f))
>   = if eq_int(n,1)
>   then i
>   else chain_item(n-1,f(i))
>
> which can be called to request the nth (12th) prime number beginning at 1.
>
> - chain_item(12,primes(1));
> GC #0.0.0.1.3.61:   (1 ms)
> val it = 37 : int
> -
>
> So I guess the answer to your question about whether the function is ever
> called with a different value may be, yes.

Actually, it's not calling it with another value; notice that
chain_item calls f(i), with i coming directly from the chain.
Consider this alternate definition:
(I'm not sure the syntax is exactly right, but you get the idea)

datatype chain =
  Link of (int * ( unit -> chain ))

fun intsFrom(n) = fun unit => (n, intsFrom (n+1))
fun ints(n) = intsFrom n ()

Now you *can't* call the function embedded in the link with another value.

fun chain_item(n,Link(i,f))
  = if eq_int(n,1)
  then i
  else chain_item(n-1,f unit)

And this type for "chain" is almost the same as [Int] in Haskell, due
to laziness.

  -- ryan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about IO, interact functions,

[Jason Dusek]

2009/05/19 David Leimbach :
> ...I'm concerned that relying on a pure function like
> "unlines . lines" to sequence IO is a bit too implicit in nature.

  You aren't relying on `unlines . lines` to do the sequencing;
  you're relying on them to process a string. That the
  characters of the string come in order has everything to do
  with `getContents`, which is trustworthy.

--
Jason Dusek
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Question about IO, interact functions,

[David Leimbach]

main = interact (unlines . lines)
This *appears* to somewhat reliably get me functionality that looks like
take a line of input, and print it out.

Is this behavior something I can rely on working?

I like the idea that lines can pull lines lazily from "getContents" which
lazily consume the input.  But I'm concerned that relying on a pure function
like "unlines . lines" to sequence IO is a bit too implicit in nature.

I really like the idea of doing things through functions like Interact in
that they appear to allow me to keep most of my code pure, but if I can't
get the IO sequencing I want to be guaranteed to work, I suppose I'll have
to dive back into "imperative IO" land that I get from the IO Monad.

Should I feel guilty for doing so?  :-)

Dave
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] showing a user defined type

[Miguel Mitrofanov]

michael rice wrote on 19.05.2009 18:16:

Cool!

Is there *anything* Haskell *can't* do?


Well, I haven't found a way to emulate polymorphics kinds yet, and I feel like 
I need them. Other than than - probably no.




Michael

--- On *Mon, 5/18/09, David Menendez //* wrote:


From: David Menendez 
Subject: Re: [Haskell-cafe] showing a user defined type
To: "Ryan Ingram" 
Cc: haskell-cafe@haskell.org
Date: Monday, May 18, 2009, 10:26 PM

On Mon, May 18, 2009 at 10:02 PM, Ryan Ingram > wrote:
 > Unfortunately, you can't derive Show on Chain as defined, because it
 > contains a function:

Sure you can. I just tried the following, and it compiled without
complaints.

 > import Text.Show.Functions
 >
 > data Chain = Link Int (Int -> Chain) deriving (Show)

The usual warnings about orphan instances apply, but the purpose of
the Text.Show.Functions module is to provide a standard Show instance
for functions so that libraries (e.g., QuickCheck) don't declare
conflicting instances.

-- 
Dave Menendez >

>
___
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 mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

RE: [Haskell-cafe] Request for feedback: HaskellDB + HList

[Brian Bloniarz]

Hi Justin,

I updated my changes to apply against that repo, thanks for 
the pointer. Cool to see new changes to haskelldb, especially
all the new unit tests!

You can find my updated repo at:
http://patch-tag.com/r/haskelldb-hlist
Re-reading your email now, I see you asked for a patch, but seeing
patch-tag for the first time I got excited and uploaded a whole new
repo, whoops.

Anyway, I had to do some minor surgery to update to the new
version -- everything compiles, but I haven't tested much beyond that
yet. Let me know if you have any questions.

Thanks,
-Brian

> I like the direction you are going. I looked into using HList a year
> or so ago and I wasn't quite up to it.  The latest (unreleased)
> version of HaskellDB is on patch-tag at
> http://patch-tag.com/r/haskelldb/snapshot/current/content/pretty.
> Would you mind creating a patch file against that for easier review? I
> won't commit it until you say its ready but I'd like to see what
> changes you have made.
> 
> No announcement has been made but I took over maintainership from
> Bjorn a few months ago. I hope to get a 1.0 release of HaskellDB out
> this summer, and having something new like this in it would be pretty
> sweet.
> 
> On Sat, May 16, 2009 at 3:08 PM, Brian Bloniarz  wrote:
> > Hi,
> >
> > It's come time to share something that I've been playing around with
> > recently:
> > a branch of HaskellDB which replaces the home-grown Record code with HList
> > records. It's definitely not ready for primetime, but I thought it'd be a
> > good
> > time to post the code and solicit some feedback from the community.
> >
> > HaskellDB the concept is very promising, but IMHO the code still falls short
> > of that promise. Hopefully this is a small step in the right direction --
> > the
> > advantages of using HList:
> > * Shared implementation of extensible records
> > * Additional features from HList
> >   * Better error messages for record misuse
> >   * "Lacks" predicates
> > * Simpler code
> >
> > As an example of how this can be better, a DB insert looks like so:
> >> insert db table $ constantRecord $
> >> film .=. "Munchie" .*.
> >> director .=. Just "Jim Wynorski" .*.
> >> emptyRecord
> > The columns need not appear in the same order as in the database. If you
> > forget
> > a column, you'll get "error: No instance for (Fail (FieldNotFound (Proxy
> > Director)))"
> > rather than an opaque error. Using the new "insertOpt" function, Maybe
> > columns
> > will default to Nothing rather than needing to be specified.
> >
> > The details:
> >
> > I haven't updated everything, but there's enough to run test/TestCases.hs
> > under Postgresql. TestCases is probably the best place to look for examples
> > of
> > the new syntax for now.
> >
> > HList had name conflicts with HaskellDB's SQL expression language
> > ((.*.), (.++.), etc.) My temporary band-aid is to move the expression
> > functions
> > to Database.HaskellDB.SqlExpr, and require people to import qualified.
> >
> > The Attr type is gone, columns labels are untyped now. I also replaced a
> > few instances of primitive type-level recursion with HMap/HMapOut. This
> > makes
> > the code simpler, and the type signatures more complex -- type families
> > would
> > help a lot here, I think.
> >
> > Feedback welcome! You can find my darcs tree at:
> >
> > http://mysite.verizon.net/vzewxzuh/sitebuildercontent/sitebuilderfiles/haskelldb-hlist-20090516.tar.gz
> > It also requires minor changes to HList, available at:
> >
> > http://mysite.verizon.net/vzewxzuh/sitebuildercontent/sitebuilderfiles/hlist-20090516.tar.gz
> > I'll talk to the HList people about getting those merged.
> >
> > Thanks!
> >
> > Brian Bloniarz
> >
> >
> > 
> > Hotmail® has a new way to see what's up with your friends. Check it out.
> > ___
> > Haskell-Cafe mailing list
> > Haskell-Cafe@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> >

_
Hotmail® has ever-growing storage! Don’t worry about storage limits.
http://windowslive.com/Tutorial/Hotmail/Storage?ocid=TXT_TAGLM_WL_HM_Tutorial_Storage1_052009___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] How to use Data.ByteString ?

[Chaddaï Fouché]

On Tue, May 19, 2009 at 8:46 AM, Brandon S. Allbery KF8NH
 wrote:
> On May 19, 2009, at 01:42 , Jason Dagit wrote:
>>
>> I've often seen this bit of scary code in VB:
>> Dim i as Integer = 5
>> If i = "5" Then
>>  ' Do something, because 5 = "5"
>> End If
>
> Sure, that works in Perl too.

That's because in numeric context Perl convert strings into numbers,
so even 5 == "5 coffees" would be true... But 5 eq "5 coffees"
wouldn't since eq force a string context and 5 is converted to "5"
which is not string-equal to "5 coffees".
Perl is all about context and is coherent in its weirdness, whereas VB
is pretty screwed IIRC.

-- 
Jedaï
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] showing a user defined type

[michael rice]

Cool!

Is there *anything* Haskell *can't* do?

Michael

--- On Mon, 5/18/09, David Menendez  wrote:

From: David Menendez 
Subject: Re: [Haskell-cafe] showing a user defined type
To: "Ryan Ingram" 
Cc: haskell-cafe@haskell.org
Date: Monday, May 18, 2009, 10:26 PM

On Mon, May 18, 2009 at 10:02 PM, Ryan Ingram  wrote:
> Unfortunately, you can't derive Show on Chain as defined, because it
> contains a function:

Sure you can. I just tried the following, and it compiled without complaints.

> import Text.Show.Functions
>
> data Chain = Link Int (Int -> Chain) deriving (Show)

The usual warnings about orphan instances apply, but the purpose of
the Text.Show.Functions module is to provide a standard Show instance
for functions so that libraries (e.g., QuickCheck) don't declare
conflicting instances.

-- 
Dave Menendez 

___
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] showing a user defined type

[michael rice]

Thanks.

I had put together something similar to your first suggestion but tried to use 
PutStrLn(Show...). I'd also thought of your second suggestion about a dummy 
show for functions.

A little further along in "The Little MLer" the ints function is replaced by 
other functions like primes and fibs, which also return Links:

fun primes(n)
  = if is_prime(n+1)
 then Link(n+1,primes)
 else primes(n+1)

fun fibs(n)(m)
  = Link(n+m,fibs(m))

which are passed to chain_item:

fun chain_item(n,Link(i,f))
  = if eq_int(n,1)
  then i
  else chain_item(n-1,f(i))

which can be called to request the nth (12th) prime number beginning at 1.

- chain_item(12,primes(1));
GC #0.0.0.1.3.61:   (1 ms)
val it = 37 : int
- 

So I guess the answer to your question about whether the function is ever 
called with a different value may be, yes.

Michael

--- On Mon, 5/18/09, Ryan Ingram  wrote:

From: Ryan Ingram 
Subject: Re: [Haskell-cafe] showing a user defined type
To: "Brandon S. Allbery KF8NH" 
Cc: "michael rice" , haskell-cafe@haskell.org
Date: Monday, May 18, 2009, 10:02 PM

Unfortunately, you can't derive Show on Chain as defined, because it
contains a function:

> data Chain = Link Int (Int -> Chain)

You can write this:

> instance Show Chain where
>    show (Link n _) = "Link " ++ show n ++ " "

Or you can make a dummy "Show" instance for functions:

> instance Show (a -> b) where show _ = ""
> data Chain = Link Int (Int -> Chain) deriving Show

One question: Do you expect to ever call the function with a different
value?  For example:

otherChain :: Chain
otherChain = case (ints 0) of Link _ f -> f 100

If not, you can replace Chain entirely by [Int], due to laziness,
something that's not possible in ML.  (Although you can get the same
result in ML by using (int * (() -> chain)) instead.

  -- ryan

On Mon, May 18, 2009 at 6:36 PM, Brandon S. Allbery KF8NH
 wrote:
> On May 18, 2009, at 21:19 , michael rice wrote:
>
> *Main> :t ints 0
> ints 0 :: Chain
> *Main> ints 0
>
> :1:0:
>     No instance for (Show Chain)
>
> In general, you want to append
>     deriving Show
> to your types.  You may also want to be able to input them in ghci, so
> instead say
>     deriving (Show, Read)
> --
> brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com
> system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu
> electrical and computer engineering, carnegie mellon university    KF8NH
>
>
> ___
> 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] fast Eucl. dist. - Haskell vs C

[Kenneth Hoste]

On May 19, 2009, at 13:24 , Daniel Schüssler wrote:


Hello!

On Monday 18 May 2009 14:37:51 Kenneth Hoste wrote:

I'm mostly interested in the range 10D to 100D


is the dimension known at compile-time? Then you could consider  
Template

Haskell.


In general, no. :-)

It will be known for some applications, but not for others.

I'm more and more amazed what comes into play just to implement
something simple like n-dim. Euclidean distance relatively fast using  
Haskell.


It seems to me that GHC is missing several critical optimizations
(yes, I know, patches welcome) to enable it to emit fast code
for HPC applications.

I'm still a big fan of Haskell, for a variety of reasons, but it seems
like it's not ready yet for the task I had in mind, which is a shame.

Just to be clear, this isn't a flame bait post or anything, just my 2  
cents.


K.


I wrote up some code for generating the vector types and vector
subtraction/inner product below, HTH. One problem is that I'm using a
typeclass and apparently you can't make {-# SPECIALISE #-} pragmas  
with TH,

so let's hope it is automatically specialised by GHC.

Greetings,
Daniel

TH.hs
--


{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS -fglasgow-exts #-}

module TH where

import Language.Haskell.TH
import Control.Monad

-- Non-TH stuff
class InnerProductSpace v r | v -> r where
   innerProduct :: v -> v -> r

class AbGroup v where
   minus :: v -> v -> v

euclidean x y = case minus x y of
 z -> sqrt $! innerProduct z z

-- TH
noContext :: Q Cxt
noContext = return []
strict :: Q Type -> StrictTypeQ
strict = liftM ((,) IsStrict)

makeVectors :: Int -- ^ Dimension
   -> Q Type -- ^ Component type, assumed to be a 'Num'
   -> String -- ^ Name for the generated type
   -> Q [Dec]
makeVectors n ctyp name0 = do
 -- let's assume ctyp = Double, name = Vector for the comments

 -- generate names for the variables we will need
 xs <- replicateM n (newName "x")
 ys <- replicateM n (newName "y")

 let
 name = mkName name0

 -- shorthands for arithmetic expressions; the first takes  
expressions,

 -- the others take variable names
 sumE  e1 e2 = infixE (Just   e1)  [|(+)|] (Just   e2)
 varDiffE e1 e2  = infixE (Just (varE e1)) [|(-)|] (Just (varE  
e2))
 varProdE e1 e2  = infixE (Just (varE e1)) [|(*)|] (Just (varE  
e2))



 conPat vars = conP name (fmap varP vars)

 -- > data Vector = Vector !Double ... !Double
 theDataD =
 dataD noContext name [] -- no context, no params
   [normalC name (replicate n (strict ctyp))]
   [''Eq,''Ord,''Show] -- 'deriving' clause

 innerProdD =
 -- > instance InnerProductSpace Vector Double where ...
 instanceD noContext ( conT ''InnerProductSpace
   `appT` conT name
   `appT` ctyp)
   -- > innerProduct = ...
   [valD
(varP 'innerProduct)
(normalB
 -- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn)  
->

 (lamE [conPat xs, conPat ys]
  -- x1*y1 +  + xn*yn + 0
  (foldl sumE [|0|] $
 zipWith varProdE xs ys)
  ))

[] -- no 'where' clause
   ]

 abGroupD =
 instanceD noContext ( conT ''AbGroup
   `appT` conT name)
   -- > minus = ...
   [valD
(varP 'minus)
(normalB
 -- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn)  
->

 (lamE [conPat xs, conPat ys]
  -- Vector (x1-y1) ... (xn-yn)
  (foldl appE (conE name) $
 zipWith varDiffE xs ys)
  ))

[] -- no 'where' clause
   ]


 sequence [theDataD,innerProdD,abGroupD]



Main.hs
--
{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE MultiParamTypeClasses #-}

module Main where

import TH

$(makeVectors 3 [t|Double|] "Vec3")

main = print $ euclidean (Vec3 1 1 1) (Vec3 0 0 0)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


--

Kenneth Hoste
Paris research group - ELIS - Ghent University, Belgium
email: kenneth.ho...@elis.ugent.be
website: http://www.elis.ugent.be/~kehoste
blog: http://boegel.kejo.be

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Expression parsing problem

[Loup Vaillant]

Hello,

2009/5/19 leledumbo :
>> expression ::= term | term "+" expression
>> term ::= factor | factor "*" term
>> factor ::= constant | variable | "(" expression ")"
>
> Oh, left recursion. Well, it should be easy to transform:
>
> expression ::= term | moreTerm
> term ::= factor | moreFactor
> moreTerm ::= term "+" expression
> factor ::= constant | variable | "(" expression ")"
> moreFactor := factor "*" term
>
> correct?

I think not. See for instance:

> expression ::= term | moreTerm
> moreTerm ::= term "+" expression

An expression begins by a term or a moreTerm… which itself begins by a
term. You still have the left recursion problem, I think.

What you mean was probably that:

expression ::= term moreTerm
term ::= factor moreFactor
factor ::= constant | variable | "(" expression ")"
moreTerm ::= "+" expression | nothing
moreFactor ::= "*" expression | nothing
nothing ::=

Unfortunately, if this work (I'm not entirely sure), it is right
associative. Example of parsing left associative operators can be
found on the net, however.

Finally, I strongly suggest you to take a look at the Parsec library
[1] (unless you can't?). It provide a "buildExpressionParser" function
which takes care of associativity and precedence for you.

[1] http://legacy.cs.uu.nl/daan/download/parsec/parsec.html
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C

[Daniel Schüssler]

Hi,

meh, I just realised that there is no sensible way to actually 
introduce/eliminate the generated types. I'm attaching a revised version with 
fromList/toList functions. Maybe the vector type should be polymorphic and be 
an instance of Functor, Monad and Foldable? But then we really depend on 
specialisation.

Greetings,
Daniel
{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS -fglasgow-exts #-}

module TH where

import Language.Haskell.TH
import Control.Monad

-- Non-TH stuff
class InnerProductSpace v r | v -> r where
innerProduct :: v -> v -> r

class AbGroup v where
minus :: v -> v -> v

class FromToList v r | v -> r where
fromList :: [r] -> Maybe v
toList :: v -> [r]

euclidean x y = case minus x y of
  z -> sqrt $! innerProduct z z

-- TH
noContext :: Q Cxt
noContext = return []
strict :: Q Type -> StrictTypeQ
strict = liftM ((,) IsStrict)
  
makeVectors :: Int -- ^ Dimension
-> Q Type -- ^ Component type, assumed to be a 'Num'
-> String -- ^ Name for the generated type
-> Q [Dec]
makeVectors n ctyp name0 = do
  -- let's assume ctyp = Double, name = Vector for the comments
  
  -- generate names for the variables we will need
  xs <- replicateM n (newName "x")
  ys <- replicateM n (newName "y")
  lst <- newName "list"
   
  let
  name = mkName name0
  
  -- shorthands for arithmetic expressions; the first takes expressions,
  -- the others take variable names 
  sumE  e1 e2 = infixE (Just   e1)  [|(+)|] (Just   e2)
  varDiffE e1 e2  = infixE (Just (varE e1)) [|(-)|] (Just (varE e2))
  varProdE e1 e2  = infixE (Just (varE e1)) [|(*)|] (Just (varE e2))

  
  conPat vars = conP name (fmap varP vars)
  
  -- > data Vector = Vector !Double ... !Double
  theDataD = 
  dataD noContext name [] -- no context, no params
[normalC name (replicate n (strict ctyp))] 
[''Eq,''Ord,''Show] -- 'deriving' clause
  
  innerProdD = 
  -- > instance InnerProductSpace Vector Double where ...
  instanceD noContext ( conT ''InnerProductSpace 
`appT` conT name 
`appT` ctyp)  
-- > innerProduct = ...
[valD 
 (varP 'innerProduct)
 (normalB
  -- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn) ->
  (lamE [conPat xs, conPat ys]
   -- x1*y1 +  + xn*yn + 0
   (foldl sumE [|0|] $
  zipWith varProdE xs ys)
   ))
   
 [] -- no 'where' clause
]
  
  abGroupD = 
  instanceD noContext ( conT ''AbGroup
`appT` conT name)  
-- > minus = ...
[valD 
 (varP 'minus)
 (normalB
  -- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn) ->
  (lamE [conPat xs, conPat ys] 
   -- Vector (x1-y1) ... (xn-yn)
   (foldl appE (conE name) $
  zipWith varDiffE xs ys)
   ))
   
 [] -- no 'where' clause
]
  
  fromToListD =
  instanceD noContext ( conT ''FromToList
`appT` conT name
`appT` ctyp)  
[ funD 'fromList
  [ clause [listP $ fmap varP xs]
 (normalB
  ([|Just|] `appE`
   (foldl appE (conE name) $ fmap varE xs)))
[]
  , clause [wildP] (normalB [|Nothing|]) [] -- wrong number 
of elements
  ]
, funD 'toList
  [ clause [conPat xs]
 (normalB
  (listE (fmap varE xs)))
[]]
]
   

  

  sequence [theDataD,innerProdD,abGroupD,fromToListD]
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C

[Claus Reinke]

I understand from your later post that is was in fact specialized, but
how do I make sure it _is_ specialized? 


-ddump-tc seems to give the generalized type, so it seems you'd need
to look at the -ddump-simpl output if you want to know whether a
local function is specialized.

http://www.haskell.org/haskellwiki/Performance/GHC#Looking_at_the_Core

Can I just add a type signature in the dist_fast definition for euclidean, 


If you need it at exactly one type, that is the simplest way. There's
also the SPECIALIZE pragma

http://www.haskell.org/ghc/docs/latest/html/users_guide/pragmas.html#specialize-pragma

and for local and non-exported functions '-O' should enable auto-specialization

http://www.haskell.org/ghc/docs/latest/html/users_guide/faster.html



After that, unrolling the fused fold loop (uvector internal) might  
help a bit, but isn't there yet:


http://hackage.haskell.org/trac/ghc/ticket/3123
http://hackage.haskell.org/trac/ghc/wiki/Inlining

And even if that gets implemented, it doesn't apply directly to your
case, where the loop is in a library, but you might want to control  
its unrolling in your client code. Having the loop unrolled by a default
factor (8x or so) should help for loops like this, with little  
computation.


This seems rather serious, and might be one of the bigger reasons why
I'm getting nowhere close to C in terms of performance...


You should be able to get near (a small factor) without it, but not having 
it leaves a substantial gap in performance, especially for simple loop 
bodies (there is also the case of enabling fusion over multiple loop 
iterations, but that may call for proper fix-point fusion).



The loop body is ridiculously small, so it would make sense to
unroll it somewhat to help avoid the loop overhead.
However, it seems like GHC isn't able to do that now.


Apart from the links above, the new backend also has relevant TODO
items: http://hackage.haskell.org/trac/ghc/wiki/BackEndNotes


Is there any way to unroll the loop myself, to speed things up?
Seems hard, because I'm using uvector...


You could 'cabal unpack' uvector, hand-unroll the core loop all
its operations get fused into, then reinstall the modified package..
(perhaps that should be a package configuration option, at least
until GHC gets loop or recursion unrolling - since this would be
a temporary workaround, it would probably not be worth it to 
have multiple package versions with different unroll factors; if
this actually helps uvector users with performance in practice, 
they could suggest it as a patch).


Claus


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C

[Daniel Schüssler]

Hello!

On Monday 18 May 2009 14:37:51 Kenneth Hoste wrote:
> I'm mostly interested in the range 10D to 100D

is the dimension known at compile-time? Then you could consider Template 
Haskell. I wrote up some code for generating the vector types and vector 
subtraction/inner product below, HTH. One problem is that I'm using a 
typeclass and apparently you can't make {-# SPECIALISE #-} pragmas with TH, 
so let's hope it is automatically specialised by GHC.

Greetings,
Daniel

TH.hs
--


{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS -fglasgow-exts #-}

module TH where

import Language.Haskell.TH
import Control.Monad

-- Non-TH stuff
class InnerProductSpace v r | v -> r where
innerProduct :: v -> v -> r

class AbGroup v where
minus :: v -> v -> v

euclidean x y = case minus x y of
  z -> sqrt $! innerProduct z z

-- TH
noContext :: Q Cxt
noContext = return []
strict :: Q Type -> StrictTypeQ
strict = liftM ((,) IsStrict)
  
makeVectors :: Int -- ^ Dimension
-> Q Type -- ^ Component type, assumed to be a 'Num'
-> String -- ^ Name for the generated type
-> Q [Dec]
makeVectors n ctyp name0 = do
  -- let's assume ctyp = Double, name = Vector for the comments
  
  -- generate names for the variables we will need
  xs <- replicateM n (newName "x")
  ys <- replicateM n (newName "y")
   
  let
  name = mkName name0
  
  -- shorthands for arithmetic expressions; the first takes expressions,
  -- the others take variable names 
  sumE  e1 e2 = infixE (Just   e1)  [|(+)|] (Just   e2)
  varDiffE e1 e2  = infixE (Just (varE e1)) [|(-)|] (Just (varE e2))
  varProdE e1 e2  = infixE (Just (varE e1)) [|(*)|] (Just (varE e2))

  
  conPat vars = conP name (fmap varP vars)
  
  -- > data Vector = Vector !Double ... !Double
  theDataD = 
  dataD noContext name [] -- no context, no params
[normalC name (replicate n (strict ctyp))] 
[''Eq,''Ord,''Show] -- 'deriving' clause
  
  innerProdD = 
  -- > instance InnerProductSpace Vector Double where ...
  instanceD noContext ( conT ''InnerProductSpace 
`appT` conT name 
`appT` ctyp)  
-- > innerProduct = ...
[valD 
 (varP 'innerProduct)
 (normalB
  -- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn) ->
  (lamE [conPat xs, conPat ys]
   -- x1*y1 +  + xn*yn + 0
   (foldl sumE [|0|] $
  zipWith varProdE xs ys)
   ))
   
 [] -- no 'where' clause
]
  
  abGroupD = 
  instanceD noContext ( conT ''AbGroup
`appT` conT name)  
-- > minus = ...
[valD 
 (varP 'minus)
 (normalB
  -- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn) ->
  (lamE [conPat xs, conPat ys] 
   -- Vector (x1-y1) ... (xn-yn)
   (foldl appE (conE name) $
  zipWith varDiffE xs ys)
   ))
   
 [] -- no 'where' clause
]
  

  sequence [theDataD,innerProdD,abGroupD]



Main.hs
--
{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE MultiParamTypeClasses #-}

module Main where

import TH

$(makeVectors 3 [t|Double|] "Vec3")

main = print $ euclidean (Vec3 1 1 1) (Vec3 0 0 0)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Expression parsing problem

[leledumbo]

I hope you're right. 7 pages... 1-2 nights should be enough. Thanks for all.
-- 
View this message in context: 
http://www.nabble.com/Expression-parsing-problem-tp23610457p23614011.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Expression parsing problem

[Ryan Ingram]

> Surely you didn't read my original post, do you? I have a very limited
> knowledge of Monad and I try to find a solution using my current skills
> because the due date is within two weeks. Therefore, I don't think I can
> create a Monadic parser for this.

I think you're giving up way too easily.  My claim is that learning to
make a monadic parser would actually be *faster* than implementing it
this way, and you'll be a better programmer at the end of it.

There's a great functional pearl on this at
http://www.cs.nott.ac.uk/~gmh/bib.html#pearl ; you do yourself a
disservice if you don't read it.  It's only 7 pages!

  -- ryan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: Haskell-Cafe Digest, Vol 69, Issue 38

[Tom Lokhorst]

These QuickCheck properties don't really test your sort function.
The `a' type variable will be instantiated to ().

So you will test with lists of units, like so:

ghci> quickCheck (\xs -> isSorted (reverse xs))
OK, passed 100 tests.

This can be simply solved by added a more specific type signature:
isSorted :: [Int] -> Bool

Surly, if the sort function works for Ints, it'll work for any Ord a.

- Tom

> -- Forwarded message --
> From: Ryan Ingram 
> To: Eugene Kirpichov 
> Date: Mon, 18 May 2009 13:57:04 -0700
> Subject: Re: [Haskell-cafe] Haskell in 3 Slides
> On Mon, May 18, 2009 at 11:33 AM, Eugene Kirpichov  
> wrote:
>> The main bullet point is missing: Correctness.
>>
>> How could we have forgotten quickcheck?
>>
>>> quickCheck (\xs -> sort (sort xs) == sort xs)
>> OK, 100 tests passed.
>
> I like this, but given that you have a whole slide, I might write this:
>
> isSorted :: Ord a => [a] -> Bool
> isSorted [] = True
> isSorted [x] = True
> isSorted (x:y:rest) = x <= y && isSorted (y:rest)
>
>> quickCheck (\xs -> isSorted (sort xs))
> OK, 100 tests passed.
>
> Or, if you want to lead into a talk about fusion and/or higher order 
> functions:
>
> isSorted [] = True
> isSorted (x:xs) = snd $ foldl' check (head x, True) xs where
>    check (prevElem, restSorted) thisElem = (thisElem, prevElem <=
> thisElem && restSorted)
>
>  -- ryan
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GUIs, FRP, (Delimited) Continuations and Zippers

[Wolfgang Jeltsch]

Am Samstag, 16. Mai 2009 16:18 schrieb GüŸnther Schmidt:
> Hi all,
>
> In my app, there is one part which has a rather complicated GUI logic,
> it involves n drop downs with n choices each.
>
> Whenever the current selection in one of the drop downs changes by user
> interaction, the other (n-1) drop downs need to be notified and their
> item list need to possible change too.
>
> Now I have managed to code all this and it actually behaves correctly.
> But I'm also using tons of IORefs and tons of bookkeeping code for it.
> While I'd not be ashamed to show any other part of my code to another
> Haskeller, this part of the code is the most clumsiest I've ever written.
>
> And I have no clue if that piece of code *can* be written in any other
> way, ie. without the tons of IORefs and bookkeeping.
>
> The GUI library is WXHaskell.
>
> In the last few days I read up on Conal Elliotts FRP stuff (reactive)
> but also on Olegs ZFS (Zippers, Delimited Continuations), the latter
> leaving me totally baffled.
>
> Could either of those approaches (FRP / Delimited Continuations) be a
> solution for implementing complex GUI code?
>
> Günther

Hello Günther,

FRP can definitely help you a lot for these kinds of problems. You have n 
widgets where each widget outputs a discrete signal (event (stream)) of 
requests from the user. These are transformed and combined to form signals 
(behaviors) that describe the contents of the n widgets over time.

Have you looked at Grapefruit? It’s an FRP library, I’m developing, which 
already has integrated GUI support. If you want to try it out, better take 
the darcs version instead of the released version since there have been some 
important developments since the release date. You find Grapefruit’s homepage 
here: . If you have questions, 
please ask.

Best wishes,
Wolfgang
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: [Haskell] [ANN] Safe Lazy IO in Haskell

[Ryan Ingram]

On Tue, May 19, 2009 at 12:54 AM, Miguel Mitrofanov
 wrote:
> I've posted it once or twice.
>
> newtype C m r a = C ((a -> m r) -> m r)
>
> It's a monad, regardless of whether m is one or not. If you have something
> like "return" and "bind", but not exactly the same, you can make "casting"
> functions
>
> m a -> C m r a
>
> and backwards.

This isn't great, though.  Consider this (slightly generalized) version:

> newtype CpsM c t a = CpsM { unCpsM :: forall b. c b -> (a -> t b) -> t b }

We can easily make this a monad for any c & t:

> instance Monad (CpsM c t) where
> return x = CpsM $ \_ k -> k x
> m >>= f  = CpsM $ \c k -> unCpsM m c $ \x -> unCpsM (f x) c k

Here's a useful one:

> -- reify Ord constraint in a data structure
> data OrdConstraint a where
> HasOrd :: Ord a => OrdConstraint a
> type M = CpsM OrdConstraint S.Set

along with your "casting" functions:

> liftS :: S.Set a -> M a
> liftS s = CpsM $ \...@hasord k -> S.unions $ map k $ S.toList s

> runS :: Ord a => M a -> S.Set a
> runS m = unCpsM m HasOrd S.singleton

Now consider this code:

> inner = do
>x <- liftS (S.fromList [1..3])
>y <- liftS (S.fromList [1..3])
>return (x+y)

> outer = do
>x <- inner
>y <- inner
>return (x+y)

If you evaluate (runS outer), eventually you get to a state like this:

= let f x = inner >>= \y -> return (x+y)
  g x2 = liftS (S.fromList [1..3]) >>= \y2 -> return (x2+y2)
  h = HasOrd
  k = \a2 -> unCpsM (g a2) h $ \a -> unCpsM (f a) h S.singleton
in S.unions $ map k [1,2,3]

which, after all the evaluation, leads to this:

= S.unions
  [S.fromList [4,5,6,7,8,9,10],
   S.fromList [5,6,7,8,9,10,11],
   S.fromList [6,7,8,9,10,11,12]]

We didn't really do any better than if we just stuck everything in a
list and converted to a set at the end!

Compare to the result of the same code using the restricted monad
solution (in this case runS = id, liftS = id):

inner >>= \x -> inner >>= \y -> return (x+y)
= (Set [1,2,3] >>= \x -> Set [1,2,3] >>= \y -> return (x+y))
  >>= \x -> inner >>= \y -> return (x+y)
= (S.unions (map (\x -> Set [1,2,3] >>= \y -> return (x+y)) [1,2,3]))
  >>= \x -> inner >>= \y -> return (x+y)
= S.unions [Set [2,3,4], Set [3,4,5], Set [4,5,6]]
  >>= \x -> inner >>= \y -> return (x+y)
= Set [2,3,4,5,6]
  >>= \x -> inner >>= \y -> return (x+y)

Notice how we've already snipped off a bunch of the computation that
the continuation-based version ran; the left-associated >>= let us
pre-collapse parts of the set down, which we will never do until the
end of the CPS version.  (This is obvious if you notice that in the
CPS version, the only HasOrd getting passed around is for the final
result type; we never call S.unions at any intermediate type!)

Of course, you can manually cache the result yourself by wrapping "inner":

> cacheS = liftS . runS
> inner_cached = cacheS inner

A version of "outer" using this version has the same behavior as the
non-CPS version.  But it sucks to have to insert the equivalent of
"optimize this please" everywhere in your code :)

  -- ryan

>
> Jason Dusek wrote on 19.05.2009 10:23:
>>
>> 2009/05/18 Miguel Mitrofanov :
>>>
>>> On 19 May 2009, at 09:06, Ryan Ingram wrote:
>>>
 This is a common problem with trying to use do-notation; there are
 some cases where you can't make the object an instance of Monad.  The
 same problem holds for Data.Set; you'd can write

 setBind :: Ord b => Set a -> (a -> Set b) -> Set b
 setBind m f = unions (map f $ toList m)

 but there is no way to use setBind for a definition of >>=
>>>
>>> You can use a continuation trick.
>>
>>  Trick?
>>
>> --
>> Jason Dusek
>> ___
>> 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 mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Expression parsing problem

[leledumbo]

> Why is Symbol = (String, Token)?  A more sensible token type would
> include values in the Value constructor and string identifiers in the
> Identifier constructor; the strings in everything else seem redundant.

Surely you didn't read my original post, do you? I have a very limited
knowledge of Monad and I try to find a solution using my current skills
because the due date is within two weeks. Therefore, I don't think I can
create a Monadic parser for this.
-- 
View this message in context: 
http://www.nabble.com/Expression-parsing-problem-tp23610457p23612618.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

RE: [Haskell-cafe] Re: [Haskell] [ANN] Safe Lazy IO in Haskell

[Sittampalam, Ganesh]

Nicolas Pouillard wrote:
> Excerpts from Ryan Ingram's message of Tue May 19 10:23:01 +0200 2009:
>> To be fair, you can do this with some extensions; I first saw this in
>> a paper on Oleg's site [1].  Here's some sample code:
> 
> This seems like the same trick as the rmonad package:
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/rmonad

It's similar, but rmonad uses an associated datatype to wrap up the
constraint, and doesn't split the Monad class up into separate pieces
(which generally makes type inference harder).

rmonad also supplies an embedding to turn any restricted monad into a
normal monad at the cost of using embed/unEmbed to get into and out of
the embedding.

Ganesh

=== 
 Please access the attached hyperlink for an important electronic 
communications disclaimer: 
 http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html 
 
=== 
 
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Expression parsing problem

[Ryan Ingram]

Why is Symbol = (String, Token)?  A more sensible token type would
include values in the Value constructor and string identifiers in the
Identifier constructor; the strings in everything else seem redundant.

A more pure/monadic parser would have a type like this:

data Result a = Error String | OK [a]
newtype Parser a = Parser (ASL -> Result (ASL, a))

Try to write these functions:

return :: a -> Parser a
(>>=) :: Parser a -> (a -> Parser b) -> Parser b

Next write some simple state modification:

token :: Parser Token
(or, if you insist on your symbol type)
token :: Parser Symbol

expect :: Token -> Parser ()

Then build on these to write:

expression :: Parser Expression
term :: Parser Expression
factor :: Parser Expression

for some suitable type Expression

Good luck, sounds like a tough but interesting project!

  -- ryan

On Mon, May 18, 2009 at 11:28 PM, leledumbo  wrote:
>
> I'm writing a paper as a replacement for writing exam and decided to write
> a simple compiler (got a little experience with it). However, I got trouble
> in parsing expression.
>
> The grammar:
> expression  = "get" | [ "+" | "-" ] term { ( "+" | "-" ) term }
>  term      = factor { ( "*" | "/" ) factor }
>    factor  = IDENTIFIER | VALUE | "(" expression ")"
>
> I can't make term parse, for instance "1 * 2 / 3" (the number is not
> important,
> identifier is also accepted). It stops after parsing 2, i.e. only the first
> multiplication is parsed. Interchanging * and / gives the same result, only
> differs in operation. Whichever got encountered first will be parsed.
>
> The same problem also arises from expression, where it can't parse "1 + 2 -
> 3".
> Both problems are identical, but I can't figure out what's wrong (don't
> count
> the optional +/- before term in expression, I haven't done it yet).
>
> Sorry, but I'm lack of knowledge about Monad. I know it can be done better
> with it,
> but I need to learn a lot about it, while I don't have enough time (only 2
> weeks).
>
> Below are necessary definitions for the parser (some taken from the
> scanner).
>
> For testing purpose, please try:
> expression
> [("1",Value),("+",Plus),("2",Value),("-",Minus),("3",Value),("EOF",EOF)]
> term
> [("1",Value),("*",Times),("2",Value),("/",Slash),("3",Value),("EOF",EOF)]
> expression
> [("1",Value),("-",Minus),("2",Value),("+",Plus),("3",Value),("EOF",EOF)]
> term
> [("1",Value),("/",Slash),("2",Value),("*",Times),("3",Value),("EOF",EOF)]
>
>> data Token = Identifier | OpenBlock | CloseBlock | SemiColon | Slash |
>>                Equals   | OpenBrace | CloseBrace |   Minus   | Times |
>>                 Plus    |    Nil    |   Value    |    Var    | Const |
>>                 Put     |    Get    |   Comma    |    EOF
>>              deriving (Show,Eq)
>
>> type Symbol = (String,Token)
>> type ASL    = [Symbol]
>
>
>> type ParseFunc = ASL -> (ASL,[String])
>
>> expression :: ParseFunc
>> expression (h:s)
>>   | snd h == Get           = (s,["IN"])
>>   | op `elem` [Plus,Minus] = (s2,r1 ++ r2 ++ [operation op])
>>   | otherwise              = (s1,r1)
>>   where (s1,r1) = term (h:s)
>>         (s2,r2) = term $ tail s1
>>         op      = if s1 /= [] then snd $ head s1 else Nil
>> expression s    = (s,[])
>
>> term :: ParseFunc
>> term s = if op `elem` [Times,Slash]
>>   then (s2,r1 ++ r2 ++ [operation op])
>>   else (s1,r1)
>>   where (s1,r1) = factor s
>>         (s2,r2) = factor $ tail s1
>>         op      = if s1 /= [] then snd $ head s1 else Nil
>
>> factor :: ParseFunc
>> factor ((id,Identifier):s) = (s,["LOAD " ++ id])
>> factor ((val,Value):s)     = (s,["PUSH " ++ val])
>> factor (("(",OpenBrace):s) = if head s1 == (")",CloseBrace)
>>   then (tail s1,r1)
>>   else error $ "\")\" expected, got" ++ (show $ fst $ head s1)
>>   where (s1,r1) = expression s
>> factor s = (s,[])
>
> --
> View this message in context: 
> http://www.nabble.com/Expression-parsing-problem-tp23610457p23610457.html
> Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
>
> ___
> 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] Re: [Haskell] [ANN] Safe Lazy IO in Haskell

[Ryan Ingram]

Minor addition, optimize >>
(I couldn't help myself!)

  -- ryan

> instance Ord b => ConstrainedBind (S.Set a) (S.Set b) where
>type BindElem (S.Set a) = a
>m >>= f = S.unions $ map f $ S.toList m
>m >> n  = if S.null m then S.empty else n
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: [Haskell] [ANN] Safe Lazy IO in Haskell

[Nicolas Pouillard]

Excerpts from Ryan Ingram's message of Tue May 19 10:23:01 +0200 2009:
> To be fair, you can do this with some extensions; I first saw this in
> a paper on Oleg's site [1].  Here's some sample code:

This seems like the same trick as the rmonad package:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/rmonad

-- 
Nicolas Pouillard
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: [Haskell] [ANN] Safe Lazy IO in Haskell

[Miguel Mitrofanov]

I've posted it once or twice.

newtype C m r a = C ((a -> m r) -> m r)

It's a monad, regardless of whether m is one or not. If you have something like "return" and "bind", but not exactly the same, you can make 
"casting" functions


m a -> C m r a

and backwards.

Jason Dusek wrote on 19.05.2009 10:23:

2009/05/18 Miguel Mitrofanov :

On 19 May 2009, at 09:06, Ryan Ingram wrote:


This is a common problem with trying to use do-notation; there are
some cases where you can't make the object an instance of Monad.  The
same problem holds for Data.Set; you'd can write

setBind :: Ord b => Set a -> (a -> Set b) -> Set b
setBind m f = unions (map f $ toList m)

but there is no way to use setBind for a definition of >>=

You can use a continuation trick.


  Trick?

--
Jason Dusek
___
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] Re: [Haskell] [ANN] Safe Lazy IO in Haskell

[Ryan Ingram]

To be fair, you can do this with some extensions; I first saw this in
a paper on Oleg's site [1].  Here's some sample code:

{-# LANGUAGE NoImplicitPrelude, TypeFamilies, MultiParamTypeClasses #-}
module SetMonad where
import qualified Data.Set as S
import qualified Prelude as P (Monad, (>>=), (>>), return, fail)
import Prelude hiding (Monad, (>>=), (>>), return, fail)

class ConstrainedPoint pa where
type PointElem pa
return :: PointElem pa -> pa

class ConstrainedBind ma mb where
type BindElem ma
(>>=) :: ma -> (BindElem ma -> mb) -> mb
(>>) :: ma -> mb -> mb
m >> n = m >>= const n

class ConstrainedFail pa where
fail :: String -> pa

instance ConstrainedPoint (S.Set a) where
type PointElem (S.Set a) = a
return = S.singleton

instance Ord b => ConstrainedBind (S.Set a) (S.Set b) where
type BindElem (S.Set a) = a
m >>= f = S.unions $ map f $ S.toList m

test :: S.Set Int
test = do
x <- S.fromList [1,2,3]
y <- S.fromList [1,2,3]
return (x+y)

-- ghci> test
-- fromList [2,3,4,5,6]

  -- ryan

[1] http://www.okmij.org/ftp/Haskell/types.html#restricted-datatypes

On Tue, May 19, 2009 at 12:46 AM, Henning Thielemann
 wrote:
>
> On Mon, 18 May 2009, Nicolas Pouillard wrote:
>
>> Excerpts from Jason Dusek's message of Sun May 17 15:45:25 +0200 2009:
>>>
>>>  From the documentation:
>>>
>>>  "  LI could be a strict monad and a strict applicative functor.
>>>    However it is not a lazy monad nor a lazy applicative
>>>    functor as required Haskell. Hopefully it is a lazy
>>>    (pointed) functor at least.
>>
>> The type I would need for bind is this one:
>>
>>  (>>=) :: NFData sa => LI sa -> (sa -> LI b) -> LI b
>>
>> And because of the NFData constraint this type bind is less general than
>> the
>> required one.
>
> Looks very similar to the operator I need for binding with respect to
> asynchronous exceptions:
>
> bind :: (Monoid a, Monad m) =>
>   ExceptionalT e m a -> (a -> ExceptionalT e m b) -> ExceptionalT e m b
> ___
> 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] Expression parsing problem

[leledumbo]

> Indeed, the grammar does not admit "1*2/3" as a sentence ...

Huh? Why not? "1 * 2 / 3" should match factor "*" factor "/" factor.
Remember that { } is repetition, so it should be able to handle such term.

> expression ::= term | term "+" expression
> term ::= factor | factor "*" term
> factor ::= constant | variable | "(" expression ")" 

Oh, left recursion. Well, it should be easy to transform:

expression ::= term | moreTerm
term ::= factor | moreFactor
moreTerm ::= term "+" expression
factor ::= constant | variable | "(" expression ")" 
moreFactor := factor "*" term

correct?
-- 
View this message in context: 
http://www.nabble.com/Expression-parsing-problem-tp23610457p23611617.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: [Haskell] [ANN] Safe Lazy IO in Haskell

[Nicolas Pouillard]

Excerpts from Taral's message of Tue May 19 00:05:39 +0200 2009:
> On Mon, May 18, 2009 at 10:30 AM, Nicolas Pouillard
>  wrote:
> > The type I would need for bind is this one:
> >
> >  (>>=) :: NFData sa => LI sa -> (sa -> LI b) -> LI b
> 
> Will this do?
> 
> (>>=) :: (NFData sa, NFData b) => LI sa -> (sa -> LI b) -> LI b

No this one would be too strict. In particular functions are not member of
NFData (and for good reasons) and we may want to have LI values holding non
"forcable" values.

However I got your idea and it can be useful.

Thanks,

-- 
Nicolas Pouillard
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] GUIs, FRP, (Delimited) Continuations and Zippers

[oleg]

> Could either of those approaches (FRP / Delimited Continuations) be a
> solution for implementing complex GUI code?

I think the answer is generally yes; I have tried writing a user
interface which has a form with several controls; a change in one
control may affect all other controls on the form (or change the
form). I have tried it for a particular GUI: the web page -- displayed
in a browser interacting with a CGI script. The choice of CGI was
deliberate because it is harder than FastCGI: it requires the ability
to save the state of the interaction. The continuation must outlive
its process. The point I was trying to make is that the GUI is
programmed as if it were a uncursed console application: you send one
question, get a reply, send another question, etc. With a GUI,
questions are sent in parallel and answers are delivered in any order;
yet the programmer can still think he deals with a regular console
application; as if the interaction never happens and the program
merely reads the data from a file.

http://okmij.org/ftp/Computation/Continuations.html#shift-cgi

It was done in OCaml though (because OCaml has native persistent
delimited continuations).
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Expression parsing problem

[Malcolm Wallace]

The grammar:
expression  = "get" | [ "+" | "-" ] term { ( "+" | "-" ) term }
 term  = factor { ( "*" | "/" ) factor }
   factor  = IDENTIFIER | VALUE | "(" expression ")"

I can't make term parse, for instance "1 * 2 / 3"


Indeed, the grammar does not admit "1*2/3" as a sentence of that  
language although it will admit "(1*2)/3" or "1*(2/3)".


If you wish to allow sequences of infix operators without bracketting,  
then examples of the standard grammar for this can be found by  
searching the web for "expression term factor", e.g. http://en.wikipedia.org/wiki/Syntax_diagram 
 suggests:


expression ::= term | term "+" expression
term ::= factor | factor "*" term
factor ::= constant | variable | "(" expression ")"

Regards,
Malcolm

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: [Haskell] [ANN] Safe Lazy IO in Haskell

[Henning Thielemann]

On Mon, 18 May 2009, Nicolas Pouillard wrote:


Excerpts from Jason Dusek's message of Sun May 17 15:45:25 +0200 2009:

  From the documentation:

 "  LI could be a strict monad and a strict applicative functor.
However it is not a lazy monad nor a lazy applicative
functor as required Haskell. Hopefully it is a lazy
(pointed) functor at least.


The type I would need for bind is this one:

 (>>=) :: NFData sa => LI sa -> (sa -> LI b) -> LI b

And because of the NFData constraint this type bind is less general than the
required one.


Looks very similar to the operator I need for binding with 
respect to asynchronous exceptions:


bind :: (Monoid a, Monad m) =>
   ExceptionalT e m a -> (a -> ExceptionalT e m b) -> ExceptionalT e m b
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C

[Kenneth Hoste]

On May 18, 2009, at 20:54 , Claus Reinke wrote:

As I said, I don't get the fusion if I just add the function above  
to the original Dist.hs, export it and compile the module with '-c  
-O2 -ddump-simpl':

I can't reproduce this.


Interesting. I'm using ghc 6.11.20090320 (windows), uvector-0.1.0.3.  
I attach the modified Dist.hs and its simpl output, created via:


  ghc -c Dist.hs -O2 -ddump-tc -ddump-simpl-stats -ddump-simpl >  
Dist.dumps


Perhaps others can confirm the effect? Note that the 'dist_fast' in  
the same module does get fused, so it is not likely an options  
issue. I still suspect that the inlining of the 'Dist.zipWith'  
wrapper in the 'dist_fast_inlined'
'__inline_me' has some significance - it is odd to see inlined code  
in an
'__inline_me' and the fusion rule won't trigger on 'Dist.sumU . Dist. 
$wzipWithU',

right?


As far as I can tell, the dist_fast_inlined doesn't get fused, i.e.  
I'm seeing

zipWithU and sumU being used in it, which is not the case in dist_fast.

This is on OS X/PowerPC, using GHC 6.10.1.


Does the complete program fragment I posted earlier yield the desired
result?


Yes. Note that the original poster also reported slowdown from
use of 'dist_fast_inlined'.


Don, you were defining dist inside the main module, while in our
case the dist functions are defined in a seperate Dist.hs module...
Would that matter?

K.

--

Kenneth Hoste
Paris research group - ELIS - Ghent University, Belgium
email: kenneth.ho...@elis.ugent.be
website: http://www.elis.ugent.be/~kehoste
blog: http://boegel.kejo.be

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C

[Kenneth Hoste]

On May 18, 2009, at 15:28 , Claus Reinke wrote:

My current best try uses the uvector package, has two 'vectors' of  
type
(UArr Double)  as input, and relies on the sumU and zipWithU  
functions

which use streaming to compute the result:
dist_fast :: UArr Double -> UArr Double -> Double
dist_fast p1 p2 = sumDs `seq` sqrt sumDs
   where
   sumDs = sumU ds
   ds= zipWithU euclidean p1 p2
   euclidean x y = d*d
   where
   d = x-y


You'll probably want to make sure that 'euclidian' is specialized to
the types you need (here 'Double'), not used overloaded for 'Num a=>a'
(check -ddump-tc, or -ddump-simpl output).


I understand from your later post that is was in fact specialized, but
how do I make sure it _is_ specialized? Can I just add a type signature
in the dist_fast definition for euclidean, or should I define euclidean
outside of dist_fast, with an explicit type signature?
If the latter, won't that hurt performance? Or should marking it INLINE
take care of that?

After that, unrolling the fused fold loop (uvector internal) might  
help

a bit, but isn't there yet:

http://hackage.haskell.org/trac/ghc/ticket/3123
http://hackage.haskell.org/trac/ghc/wiki/Inlining

And even if that gets implemented, it doesn't apply directly to your
case, where the loop is in a library, but you might want to control  
its

unrolling in your client code. Having the loop unrolled by a default
factor (8x or so) should help for loops like this, with little  
computation.


This seems rather serious, and might be one of the bigger reasons why
I'm getting nowhere close to C in terms of performance...
The loop body is ridiculously small, so it would make sense to
unroll it somewhat to help avoid the loop overhead.
However, it seems like GHC isn't able to do that now.

Is there any way to unroll the loop myself, to speed things up?
Seems hard, because I'm using uvector...

K.

--

Kenneth Hoste
Paris research group - ELIS - Ghent University, Belgium
email: kenneth.ho...@elis.ugent.be
website: http://www.elis.ugent.be/~kehoste
blog: http://boegel.kejo.be

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe