[Haskell-cafe] (no subject)

[oleg]

Martin Sulzmann wrote:
> "Undecidable" instances means that there exists a program for which there's
> an infinite reduction sequence.

I believe this may be too strong of a statement. There exists patently
terminating type families that still require undecidable
instances in GHC. Here is an example:

> {-# LANGUAGE TypeFamilies #-}
>
> type family I x :: *
> type instance I x = x
>
> type family B x :: *
> type instance B x = I x


GHC 6.8.3 complaints:
Application is no smaller than the instance head
  in the type family application: I x
(Use -fallow-undecidable-instances to permit this)
In the type synonym instance declaration for `B'

But there cannot possibly be any diverging reduction sequence here, can it?
The type family I is the identity, and the type family B is its
alias. There is no recursion. The fact that type families are open is
not relevant here: our type families I and B are effectively closed,
because one cannot define any more instance for I and B (or risk
overlap, which is rightfully not supported for type families).

The reason GHC complains is because it checks termination
instance-by-instance. To see the termination in the above program, one
should consider instances I and B together. Then we will see that I
does not refer to B, so there are no loops. But this global
termination check -- for a set of instances -- is beyond the
abilities of GHC. This is arguably the right decision: after all, GHCi
is not a full-blown theorem prover. 

Thus there are perfectly decidable type programs that require
undecidable instances. Indeed, there is no reason to be afraid of that
extension.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Fwd: [Haskell-cafe] Haskell for Physicists

[Daryoush Mehrtash]

Of all the projects that are in the HackageDB, how many, or what % do you
say developed an EDSL?

daryoush

On Tue, Oct 13, 2009 at 3:06 PM, Xiao-Yong Jin  wrote:

> Don Stewart  writes:
>
> > Hey all,
> >
> > Following up on this, I'm presenting a position paper tomorrow on the
> > use of EDSLs to improve productivity and lower cost when developing code
> > for new high performance architectures (like GPUs).
> >
> >
> http://www.galois.com/blog/2009/10/13/domain-specific-languages-for-domain-specific-problems/
> >
> > It advocates for Haskell + EDSLs, much as we have been discussing in
> > this thread.
>
> I'm very interested in EDSL in high performance
> architectures.  Can you give me some idea what the
> performance might be using code written in Haskell+EDSL
> compared to C/C++?  I think, in high performance computing,
> the efficiency in the resulting binary code largely depends
> on the problem domain.  Can haskell help a lot in optimizing
> the EDSL to machine binary?  And what would be the
> efficiency in terms of space and time?
>
> Xiao-Yong
> --
>c/*__o/*
><\ * (__
>*/\  <
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Daryoush

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

[Haskell-cafe] Re: why does "iterateNTimes (10^6) (ap . liftM (:) . return $ 0) (return [])" produce output in the IO monad, but stack overflow in the maybe monad?

[Thomas Hartman]

correction, should be:

iterateNTimes i f x = foldr (.) id (replicate i f) $ x
tntIO :: IO Int
-- same as replicateM (10^6) $ return 0
tntIO = return . head =<< (iterateNTimes (10^6) (ap . liftM (:) .
return $ 0) (return [])) -- produces output
tntMb :: Maybe Int -- overflows
tntMb = return . head =<< (iterateNTimes (10^6) (ap . liftM (:) .
return $ 0) (return [])) -- stack overflow

which now compiles.

2009/10/13 Thomas Hartman :
> Can someone explain why the one stack overflows and the other one doesn't?
>
> iterateNTimes i f x = foldr (.) id (replicate i f) $ x
> tntIO :: IO Int
> -- same as replicateM (10^6) $ return 0 , and same as sequence .
> replicate (10^6) $ return 0
> tntIO = iterateNTimes (10^6) (ap . liftM (:) . return $ ) (return [])
> -- produces output
> tntMb :: Maybe Int -- overflows
> tntMb = iterateNTimes (10^6) (ap . liftM (:) . return $ ) (return [])
> -- stack overflow
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Type-level naturals & multiplication

[Martin Sulzmann]

On Tue, Oct 13, 2009 at 9:37 AM, Simon Peyton-Jones
wrote:

> | > Is there any way to define type-level multiplication without requiring
> | > undecidable instances?
> |
> | No, not at the moment.  The reasons are explained in the paper "Type
> | Checking with Open Type Functions" (ICFP'08):
> |
> |
> http://www.cse.unsw.edu.au/~chak/papers/tc-tfs.pdf
> |
> | We want to eventually add closed *type families* to the system (ie,
> | families where you can't add new instances in other modules).  For
> | such closed families, we should be able to admit more complex
> | instances without requiring undecidable instances.
>
> It's also worth noting that while "undecidable" instances sound scary, but
> all it means is that the type checker can't prove that type inference will
> terminate.  We accept this lack-of-guarantee for the programs we *run*, and
> type inference can (worst case) take exponential time which is not so
> different from failing to terminate; so risking non-termination in type
> inference is arguably not so bad.
>
>
>
Some further details to shed some light on this topic.

"Undecidable" instances means that there exists a program for which there's
an infinite reduction sequence.
By "undecidable" I refer to instances violating the conditions in the
icfp'08
and in the earlier jfp paper "Understanding Functional Dependencies via
Constraint Handling Rules".

Consider the classic example

  Add (Succ x) x ~ x
--> Succ (Add x x) ~ x

 substitute for x and you'll get another redex of the form

 Add (Succ ..) ... and therefore the reduction won't terminate

To fix this problem, i.e. preventing the type checker to non-terminate,
we could either

 (a) spot the "loop" in Add (Succ x) x ~ x  and reject this
   unsatisfiable constraint and thus the program
 (b) simply stop after n steps

The ad-hoc approach (b) restores termination but risks incompleteness.

Approach (a) is non-trivial to get right, there are more complicated loopy
programs
where spotting the loops gets really tricky.

The bottom line is this:

Running the type checker on "undecidable" instances means that
there are programs for which

   - the type checker won't terminate, or
- wrongly rejects the program (incompleteness)

So, the situation is slightly more scary, BUT
programs exhibiting the above behavior are (in my experience)
rare/contrived.

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

Re: [Haskell-cafe] Exponential complexity of type checking (Was: Type-level naturals & multiplication)

[Dan Doel]

On Tuesday 13 October 2009 1:06:41 pm Brad Larsen wrote:
> Good example!  I have a feeling that the `dup' example is a bit
> contrived, not something that one would be likely to find in the wild.

This is, after all, why HM is useful. In general, there are programs that take 
exponential time/space to type check, but those programs don't come up much in 
real code.

Also, you can do better than 2^n:

  f0 x = (x,x)
  f1   = f0 . f0
  f2   = f1 . f1
  f3   = f2 . f2
  ...

Here, if fN results in a nested tuple of size M, then f(N+1) results in a 
tuple of size M^2, since we replace all the variables with a copy of the 
tuple. So we have 2, 4, 16, 256, ... 2^(2^N)  Turning f0 into an M-tuple 
gets you M^(2^N), I believe, and composing K times at each step would get you 
M^(K^N). But anyhow, we have not merely an exponential, but a double 
exponential. :) f4 takes a noticeable amount of time to check here (in ghci), 
and f5 makes my machine start swapping.

Of course, one isn't likely to write code like this, either.

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

Re: Fwd: [Haskell-cafe] Haskell for Physicists

[Xiao-Yong Jin]

Don Stewart  writes:

> Hey all,
>
> Following up on this, I'm presenting a position paper tomorrow on the
> use of EDSLs to improve productivity and lower cost when developing code
> for new high performance architectures (like GPUs).
>
> 
> http://www.galois.com/blog/2009/10/13/domain-specific-languages-for-domain-specific-problems/
>
> It advocates for Haskell + EDSLs, much as we have been discussing in
> this thread.

I'm very interested in EDSL in high performance
architectures.  Can you give me some idea what the
performance might be using code written in Haskell+EDSL
compared to C/C++?  I think, in high performance computing,
the efficiency in the resulting binary code largely depends
on the problem domain.  Can haskell help a lot in optimizing
the EDSL to machine binary?  And what would be the
efficiency in terms of space and time?

Xiao-Yong
-- 
c/*__o/*
<\ * (__
*/\  <
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] why does "iterateNTimes (10^6) (ap . liftM (:) . return $ 0) (return [])" produce output in the IO monad, but stack overflow in the maybe monad?

[Thomas Hartman]

Can someone explain why the one stack overflows and the other one doesn't?

iterateNTimes i f x = foldr (.) id (replicate i f) $ x
tntIO :: IO Int
-- same as replicateM (10^6) $ return 0 , and same as sequence .
replicate (10^6) $ return 0
tntIO = iterateNTimes (10^6) (ap . liftM (:) . return $ ) (return [])
-- produces output
tntMb :: Maybe Int -- overflows
tntMb = iterateNTimes (10^6) (ap . liftM (:) . return $ ) (return [])
-- stack overflow
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: Reverse dependencies in Hackage

[Duncan Coutts]

On Tue, 2009-10-13 at 21:30 +0200, Roel van Dijk wrote:

> I also noticed that work is underway to implement a new hackage-server
> [2] based on happstack. If people find this feature useful I could
> also write a patch against the hackage-server code base [3].

That would be much appreciated.

Duncan

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

Re: [Haskell-cafe] GHC core packages: same core?

[Dimitry Golubovsky]

Max,

Thanks for the explanation. So, the extcore library is expected to
match the spec in
http://www.haskell.org/ghc/docs/6.10.4/html/ext-core/core.pdf and the
core itself can be produced with -fext-core, correct? I think it might
be interesting for people working on alternative backends (inlcuding
myself).

On Tue, Oct 13, 2009 at 4:53 PM, Max Bolingbroke
 wrote:
[skip]
>
> extcore is a library that parses "external" Core, which is an
> alternative format intended to be stable and hence a suitable target
> for consumption by non-GHC tooling. You can have GHC output external
> core instead of machine code / C. I don't believe this is widely used
> yet.

-- 
Dimitry Golubovsky

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

Re: [Haskell-cafe] a library for control of terminal driver modes?

[Max Bolingbroke]

Err, I managed to completely misread your email. Sorry.

Unfortunately, ansi-terminal does NOT support disabling the echo and I
don't plan to support it. However, given that I already provide
non-ANSI features from it, patches would be happily accepted :-)

Cheers,
Max

2009/10/13 Max Bolingbroke :
> Yes, ansi-terminal supports this. Try:
>
> setSGR [SetBlinkSpeed NoBlink]
>
> (http://hackage.haskell.org/packages/archive/ansi-terminal/0.5.0/doc/html/System-Console-ANSI.html)
>
> Cheers,
> Max
>
> 2009/10/12 Iain Barnett :
>>
>> On 11 Oct 2009, at 15:30, Andrew Coppin wrote:
>>
>>> Iain Barnett wrote:

 I'm looking for a library like Perl's Term-Readkey, so that I can turn on
 and off the echo for secure password input from a terminal. Anyone know
 which library I need to use for this?
>>>
>>> The package ansi-terminal allows you to do various things to the terminal;
>>> I think it might include turning local echo on/off. Alternatively, there was
>>> an announcement recently about a text-mode UI package, which might do what
>>> you want. (I don't recall the name...)
>>>
>>
>> Thanks
>>
>>
>> Iain
>> ___
>> 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] a library for control of terminal driver modes?

[Max Bolingbroke]

Yes, ansi-terminal supports this. Try:

setSGR [SetBlinkSpeed NoBlink]

(http://hackage.haskell.org/packages/archive/ansi-terminal/0.5.0/doc/html/System-Console-ANSI.html)

Cheers,
Max

2009/10/12 Iain Barnett :
>
> On 11 Oct 2009, at 15:30, Andrew Coppin wrote:
>
>> Iain Barnett wrote:
>>>
>>> I'm looking for a library like Perl's Term-Readkey, so that I can turn on
>>> and off the echo for secure password input from a terminal. Anyone know
>>> which library I need to use for this?
>>
>> The package ansi-terminal allows you to do various things to the terminal;
>> I think it might include turning local echo on/off. Alternatively, there was
>> an announcement recently about a text-mode UI package, which might do what
>> you want. (I don't recall the name...)
>>
>
> Thanks
>
>
> Iain
> ___
> 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 core packages: same core?

[Max Bolingbroke]

Hi Dimitry,

ghc-core is a pretty-printer for GHC's internal Core language (you can
get a non-pretty-printed version simply by compiling with (IIRC)
-dverbose-core2core). This is what we actually optimize and generate
code from, and the formatting of this output might change at any time.
This is probably what you should be looking at, as a human trying to
understand how your programs are being complied.

extcore is a library that parses "external" Core, which is an
alternative format intended to be stable and hence a suitable target
for consumption by non-GHC tooling. You can have GHC output external
core instead of machine code / C. I don't believe this is widely used
yet.

Cheers,
Max

2009/10/12 Dimitry Golubovsky :
> Hi,
>
> Just curious whether package
> http://hackage.haskell.org/package/ghc-core and
> http://hackage.haskell.org/package/extcore operate on the same flavor
> of GHC Core?
>
> There seem to be external [1] and internal [2] flavors of GHC Core.
>
> [1] http://www.haskell.org/ghc/docs/6.10.2/html/ext-core/core.pdf
> [2] http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/CoreSynType
>
> Thanks.
>
> --
> Dimitry Golubovsky
>
> Anywhere on the Web
> ___
> 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] <**> for nested applicative functors?

[Conal Elliott]

Hi Kim-Ee,

This pattern shows up in "Applicative programming with effects" in showing
that the composition of applicatives is applicative: (<*>) = liftA2 (<*>),
and pure = pure.pure .  (Really, you have to manage newtype wrappers as
well.  See the TypeCompose library.)

   - Conal

On Mon, Oct 12, 2009 at 9:52 AM, Kim-Ee Yeoh  wrote:

>
> That's it: liftA2 (<*>), so obvious in hindsight.
>
> Mustn't ... code ... when ... drained 
>
> Thanks to Jeremy and Josef.
>
>
> Jeremy Shaw-3 wrote:
> >
> > This looks like what is described in Section 4 to me:
> >
> >
> http://www.haskell.org/haskellwiki/Applicative_functor#Applicative_transfomers
> >
> > - jeremy
> >
> > On Oct 12, 2009, at 11:22 AM, Kim-Ee Yeoh wrote:
> >
> >> <**> :: (Applicative m, Applicative n) =>
> >> m (n (a->b)) -> m (n a) -> m (n b)
> >
>
> --
> View this message in context:
> http://www.nabble.com/%3C**%3E-for-nested-applicative-functors--tp25858792p25859274.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

[Haskell-cafe] Reverse dependencies in Hackage

[Roel van Dijk]

A few weeks ago I wrote a patch that adds reverse dependencies to
hackage [1]. I have know hosted a small test hackage which
demonstrates this feature. It can be found here:

http://bifunctor.homelinux.net/~roel/hackage

Browse to your favorite packages and find out how much other packages
depend on them!

I also noticed that work is underway to implement a new hackage-server
[2] based on happstack. If people find this feature useful I could
also write a patch against the hackage-server code base [3].

Regards,
Roel van Dijk


[1] - http://hackage.haskell.org/trac/hackage/ticket/576
[2] - http://sparky.haskell.org:8080/
[3] - http://code.haskell.org/hackage-server/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Fwd: [Haskell-cafe] Haskell for Physicists

[Don Stewart]

Hey all,

Following up on this, I'm presenting a position paper tomorrow on the
use of EDSLs to improve productivity and lower cost when developing code
for new high performance architectures (like GPUs).


http://www.galois.com/blog/2009/10/13/domain-specific-languages-for-domain-specific-problems/

It advocates for Haskell + EDSLs, much as we have been discussing in
this thread.

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

[Haskell-cafe] Re: [Haskell-beginners] using quickcheck for blackbox testing for 3rd party apps.

[Daniel Fischer]

Am Dienstag 13 Oktober 2009 18:04:52 schrieb Brent Yorgey:
> Brent
>
> * Some smart-alecks might pipe up with something about unsafePerformIO
>   here.  But that's not a cure, it's more like performing an emergency
>   tracheotomy with a ballpoint pen.

Quote of the month!
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Exponential complexity of type checking (Was: Type-level naturals & multiplication)

[Brad Larsen]

On Tue, Oct 13, 2009 at 12:32 PM, Serguey Zefirov  wrote:
> 2009/10/13 Lennart Augustsson :
>> Yes, there are simple H-M examples that are exponential.
>> x0 = undefined
>> x1 = (x1,x1)
>> x2 = (x2,x2)
>> x3 = (x3,x3)
>> ...
>>
>> xn will have a type with 2^n type variables so it has size 2^n.
>
> Reformulated:
> let dup x = (x,x)
> :t dup . dup . dup . dup ...
>
> type will be 2^(number of dup's).
>
> I experimented and found that GHC can stand pretty long line of dup's.
> More than 20, at least.
>
> One part of our program took too much time to typecheck some time ago.
> 3 and half minutes for ~900 lines module. Most of operations was
> inside heavily parametrized monad (5 parameters, each is a Peano
> number). Then my colleague moved parameters into associated types of
> relevant type class and now it typechecks in ten seconds.
>

Good example!  I have a feeling that the `dup' example is a bit
contrived, not something that one would be likely to find in the wild.

Heavily parameterized type classes, on the other hand, are more common
in real code.  Hence, that is more likely where someone would run into
really awful type inference performance without expecting it.

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

Re: [Haskell-cafe] Exponential complexity of type checking (Was: Type-level naturals & multiplication)

[Serguey Zefirov]

2009/10/13 Lennart Augustsson :
> Yes, there are simple H-M examples that are exponential.
> x0 = undefined
> x1 = (x1,x1)
> x2 = (x2,x2)
> x3 = (x3,x3)
> ...
>
> xn will have a type with 2^n type variables so it has size 2^n.

Reformulated:
let dup x = (x,x)
:t dup . dup . dup . dup ...

type will be 2^(number of dup's).

I experimented and found that GHC can stand pretty long line of dup's.
More than 20, at least.

One part of our program took too much time to typecheck some time ago.
3 and half minutes for ~900 lines module. Most of operations was
inside heavily parametrized monad (5 parameters, each is a Peano
number). Then my colleague moved parameters into associated types of
relevant type class and now it typechecks in ten seconds.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Exponential complexity of type checking (Was: Type-level naturals & multiplication)

[Lennart Augustsson]

Yes, there are simple H-M examples that are exponential.
x0 = undefined
x1 = (x1,x1)
x2 = (x2,x2)
x3 = (x3,x3)
...

xn will have a type with 2^n type variables so it has size 2^n.

  -- Lennart

On Tue, Oct 13, 2009 at 6:04 PM, Brad Larsen  wrote:
> On Tue, Oct 13, 2009 at 3:37 AM, Simon Peyton-Jones
>  wrote:
>> | > Is there any way to define type-level multiplication without requiring
>> | > undecidable instances?
>> |
>> | No, not at the moment.  The reasons are explained in the paper "Type
>> | Checking with Open Type Functions" (ICFP'08):
>> |
>> |    http://www.cse.unsw.edu.au/~chak/papers/tc-tfs.pdf
>> |
>> | We want to eventually add closed *type families* to the system (ie,
>> | families where you can't add new instances in other modules).  For
>> | such closed families, we should be able to admit more complex
>> | instances without requiring undecidable instances.
>>
>> It's also worth noting that while "undecidable" instances sound scary, but 
>> all it means is that the type checker can't prove that type inference will 
>> terminate.  We accept this lack-of-guarantee for the programs we *run*, and 
>> type inference can (worst case) take exponential time which is not so 
>> different from failing to terminate; so risking non-termination in type 
>> inference is arguably not so bad.
>>
>> Simon
>>
>
> I have written code that makes heavy use of multi-parameter type
> classes in the ``finally tagless'' tradition, which takes several
> seconds and many megabytes of memory for GHCI to infer its type.
> However, that example is rather complicated, and I am not sure its
> type inference complexity is exponential---it is at least very bad.
>
> Are there any simple, well-known examples where Haskell type inference
> has exponential complexity?  Or Hindley-Milner type inference, for
> that matter?  (Haskell 98 is not quite Hindley-Milner?)
>
> Sincerely,
> Brad Larsen
> ___
> 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] Exponential complexity of type checking (Was: Type-level naturals & multiplication)

[Brad Larsen]

On Tue, Oct 13, 2009 at 3:37 AM, Simon Peyton-Jones
 wrote:
> | > Is there any way to define type-level multiplication without requiring
> | > undecidable instances?
> |
> | No, not at the moment.  The reasons are explained in the paper "Type
> | Checking with Open Type Functions" (ICFP'08):
> |
> |    http://www.cse.unsw.edu.au/~chak/papers/tc-tfs.pdf
> |
> | We want to eventually add closed *type families* to the system (ie,
> | families where you can't add new instances in other modules).  For
> | such closed families, we should be able to admit more complex
> | instances without requiring undecidable instances.
>
> It's also worth noting that while "undecidable" instances sound scary, but 
> all it means is that the type checker can't prove that type inference will 
> terminate.  We accept this lack-of-guarantee for the programs we *run*, and 
> type inference can (worst case) take exponential time which is not so 
> different from failing to terminate; so risking non-termination in type 
> inference is arguably not so bad.
>
> Simon
>

I have written code that makes heavy use of multi-parameter type
classes in the ``finally tagless'' tradition, which takes several
seconds and many megabytes of memory for GHCI to infer its type.
However, that example is rather complicated, and I am not sure its
type inference complexity is exponential---it is at least very bad.

Are there any simple, well-known examples where Haskell type inference
has exponential complexity?  Or Hindley-Milner type inference, for
that matter?  (Haskell 98 is not quite Hindley-Milner?)

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

Re: [Haskell-cafe] Type-level naturals & multiplication

[Brad Larsen]

On Tue, Oct 13, 2009 at 3:37 AM, Simon Peyton-Jones
 wrote:
[...]
> It's also worth noting that while "undecidable" instances sound scary, but 
> all it means is that the type checker can't prove that type inference will 
> terminate.  We accept this lack-of-guarantee for the programs we *run*, and 
> type inference can (worst case) take exponential time which is not so 
> different from failing to terminate; so risking non-termination in type 
> inference is arguably not so bad.
>
> Simon

Indeed!

On a related note, template instantiation in C++ is undecidable.  See
``C++ Templates are Turing Complete'' by Todd Veldhuizen:
.
And similarly, heavy use of templates in C++ can be *extremely*
compute-intensive.

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

Re: [Haskell-cafe] Parsec bug, or...?

[Uwe Hollerbach]

On 10/12/09, Martijn van Steenbergen  wrote:
> Brandon S. Allbery KF8NH wrote:
>> My fix would be to have myPrefixOf require the prefix be terminated in
>> whatever way is appropriate (end of input, white space, operator?)
>> instead of simply accepting as soon as it gets a prefix match regardless
>> of what follows.
>
> Maybe you can use notFollowedBy for this.
>
> HTH,
>
> Martijn.
>
>

Yes, I've looked at that and am thinking about it. I'm not quite
certain it's needed in my real program... I seem to have convinced
myself that if I actually specify a proper set of unique prefixes, ie,
set the required lengths for both "frito" and "fromage" to 3 in the
test program, I won't get into this situation. Assuming I haven't
committed another brain-fart there, that would be sufficient;
presumably, in a real program one would want to actually specify the
unique prefix, rather than a non-unique pre-prefix. It seems to work
fine in my real program, anyway.

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

[Haskell-cafe] Time Typeable Instances

[John Goerzen]

Hugo Gomes wrote:
> The Glorious Glasgow Haskell Compilation System, version 6.10.4
> with old-time-1.0.0.2 and time-1.1.2.4
> 
> This is a standard haskell platform on a windows xp. Cabal install
> didn't work complaining about missing instances of typeable for posix
> time and other datatypes, yet, after removing the macros (thus, adding
> those instances), hdbc and convertible compiled and installed fine. 
> 
> Removing the macros might be a bit overkill, probably finetuning them so
> that they add only the necessary instances for typeable in ghc > 610
> might be a better solution.

I'm going to CC haskell-cafe on this because I am confused.

Hugo, can you confirm what version of convertible you have?

Back on May 21, I started a thread [1] on haskell-cafe complaining that
GHC 6.10.3 included a newer time that included instances of Typeable for
NominalDiffTime and UTCTime.  This broke my code, which had manually
defined instances for these types, as they were needed.  Things got
complicated, as only time's minor version number got incremented
(x.x.x.Y) [2].  Cabal can't test against that version number.

I wanted my code to work with old and new versions of GHC.  Since
testing against the version of time was impossible, I did the next best
thing: tested against the version of GHC.

#if __GLASGOW_HASKELL__ >= 610
-- instances added in GHC 6.10.3
#else
instance Typeable NominalDiffTime where
typeOf _ = mkTypeName "NominalDiffTime"

instance Typeable UTCTime where
typeOf _ = mkTypeName "UTCTime"
#endif

Also, in the .cabal, there is a build-depends on time>=1.1.2.4.

Now, that would break for GHC 6.10.1 and 6.10.2 users, but will work for
6.10.3 and above, or 6.8 and below.  Or so I thought.

Now I'm getting complaints from people using 6.10.4 saying that there
are now missing instances of Typeable with time 1.1.2.4.

1) Did the Typeable instances get dropped again from time?
2) What exactly should I do so this library compiles on GHC 6.8 and 6.10.x?

I'm looking at the darcs repo for time and don't see the instances ever
getting dropped.

[1] http://osdir.com/ml/haskell-cafe@haskell.org/2009-05/msg00982.html
[2] http://osdir.com/ml/haskell-cafe@haskell.org/2009-05/msg00985.html


 later addendum 

so it appears that what's happening here is that GHC 6.10.3 extralibs
included time 1.1.3, but then haskell-platform standardized on 1.1.2.4.
 This is pretty annoying -- that haskell-platform would standardize on a
version older than what shipped with a GHC release -- but I guess I can
work around it by restricting my build-dep to be time < 1.1.3 and
re-adding the instances.

Does this sound right?

> 
> 
> On Tue, Oct 13, 2009 at 2:51 AM, John Goerzen  > wrote:
> 
> Hugo Gomes wrote:
> > Hi,
> >
> > convertible and hdbc packages fail to compile in my standard
> instalation
> > of the haskell platform. I think this has to do with those "if ghc >=
> > 610" macros on the typeable instances for some datatypes. I
> removed them
> > and now they work fine...
> >
> >
> >
> 
> 
> What version of GHC and time do you have?
> 
> -- John
> 
> 

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

RE: [Haskell-cafe] Re: Libraries for Commercial Users

[Simon Peyton-Jones]

There is no difficulty in principle with Haskell on JVM.  There are, however, 
some obstacles in practice, as this page describes:

http://haskell.org/haskellwiki/GHC:FAQ#Why_isn.27t_GHC_available_for_.NET_or_on_the_JVM.3F

The way stands open for someone with design taste, knowledge of the JVM, and 
sustained willingness to roll up sleeves, to make a significant contribution.

Simon

| -Original Message-
| From: haskell-cafe-boun...@haskell.org 
[mailto:haskell-cafe-boun...@haskell.org] On
| Behalf Of wren ng thornton
| Sent: 12 October 2009 01:54
| To: Haskell Cafe
| Subject: Re: [Haskell-cafe] Re: Libraries for Commercial Users
| 
| Patrick LeBoutillier wrote:
| > Don,
| >
| >>> Having painless Haskell <- Java interoperability would be great.  I'm
| >>> curious though:  could it really be so simple as a one-line ``import
| >>> foreign jvm'' directive?  I imagine the purity mismatch between
| >>> Haskell and Java would be very troublesome.
| >> No more so than C, surely. We're used to stateful APIs. They're a pain.
| >>
| >>
| >>> With this hypothetical ``import foreign jvm'' mechanism, what would
| >>> the be type of imported Java stuff?  Would it all be done in IO?
| >>>
| >>> The more I think about it, the trickier it seems.  Beside the purity
| >>> mismatch of Haskell and Java, there is an OO/functional mismatch.
| >> That's more of an issue. But the prior work has been done.
| >
| > Do you have any references to this work?
| 
| 
| It was a major research topic about a decade ago, though the projects
| have died since. And the topic comes up about every 4 months on the
| Cafe, so I'd recommend sifting through the archives. I know last time it
| came up (or the time before?) I gave a rather extensive list of
| projects. And the wiki[1] still lists a few of them.
| 
| The last time this discussion came up people got involved enough to
| revive LambdaVM[2], which was one of the more mature options back in the
| day. If you're interested in the topic, I suggest getting in touch with
| the author and helping out.
| 
| On the topic of automatically embedding OO-style languages into Haskell,
| you should also check out hprotoc[3]. It's a package for Google's
| protocol buffers, which are ostensibly language agnostic but actually
| assume a (weakly) OO language. The hprotoc library will create a family
| of virtual modules based on the protocol spec and makes a pretty nice
| interface out of them.
| 
| 
| [1]
| 
http://www.haskell.org/haskellwiki/Applications_and_libraries/Interfacing_other_lang
| uages
| [2] http://wiki.brianweb.net/LambdaVM/LambdaVM
| [3] http://hackage.haskell.org/package/hprotoc
| 
| --
| Live well,
| ~wren
| ___
| 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] What *is* a DSL?

[Nils Anders Danielsson]

On 2009-10-07 17:29, Robert Atkey wrote:

A deep embedding of a parsing DSL (really a context-sensitive grammar
DSL) would look something like the following. I think I saw something
like this in the Agda2 code somewhere, but I stumbled across it when I
was trying to work out what "free" applicative functors were.


The Agda code you saw may have been due to Ulf Norell and me. There is a
note about it on my web page:

 
http://www.cs.nott.ac.uk/~nad/publications/danielsson-norell-parser-combinators.html


Note that these grammars are strictly less powerful than the ones that
can be expressed using Parsec because we only have a fixed range of
possibilities for each rule, rather than allowing previously parsed
input to determine what the parser will accept in the future.


Previously parsed input /can/ determine what the parser will accept in
the future (as pointed out by Peter Ljunglöf in his licentiate thesis).
Consider the following grammar for the context-sensitive language
{aⁿbⁿcⁿ| n ∈ ℕ}:

 data NT a where
   Start ::NT ()  -- Start ∷= aⁿbⁿcⁿ
   ABC   :: Nat -> NT ()  -- ABC n ∷= aˡbⁿ⁺ˡcⁿ⁺ˡ
   X :: Char -> Nat -> NT ()  -- X x n ∷= xⁿ

 g :: Grammar NT
 g Start   =  nt (ABC 0)
 g (ABC n) =  char 'a' <* nt (ABC (succ n))
  <|> nt (X 'b' n) <* nt (X 'c' n)
 g (X c n)
   | n == 0= pure ()
   | otherwise = char c <* nt (X c (pred n))


And a general definition for parsing single-digit numbers. This works
for any set of non-terminals, so it is a reusable component that works
for any grammar:


Things become more complicated if the reusable component is defined
using non-terminals which take rules (defined using an arbitrary
non-terminal type) as arguments. Exercise: Define a reusable variant of
the Kleene star, without using grammars of infinite depth.

--
/NAD


This message has been checked for viruses but the contents of an attachment
may still contain software viruses, which could damage your computer system:
you are advised to perform your own checks. Email communications with the
University of Nottingham may be monitored as permitted by UK legislation.

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

Re: [Haskell-cafe] Haskell-tan competition

[Svein Ove Aas]

On Tue, Oct 13, 2009 at 1:12 PM, Ariel J. Birnbaum  wrote:
>> What about Lambdabot?
>
> The official (?) personification of Lambdabot is OK, but lacks moe[1],
> which the OP seems to intend by using the suffix '-tan'. In any case,
> she represents Lambdabot only, not Haskell in general.
>
A lambdabot-specific personification is fine too, but I agree that it
lacks charm.

Though I wonder, where should we put these?
Having the lambdabot one on the lambdabot page is fine, but
haskell-tan would have to be stuck on the front page. Which seems a
bit too much.

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

Re: [Haskell-cafe] Haskell-tan competition

[Ariel J. Birnbaum]

> What about Lambdabot?

The official (?) personification of Lambdabot is OK, but lacks moe[1],
which the OP seems to intend by using the suffix '-tan'. In any case,
she represents Lambdabot only, not Haskell in general.

I'll try and give this one a shot over the weekend.

Have fun!

[1] http://en.wikipedia.org/wiki/Moe_anthropomorphism

-- 
Ariel J. "askyle" Birnbaum

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

Re: [Haskell-cafe] Re: MTL vs Transformers?

[Erik de Castro Lopo]

John Lato wrote:

> Unfortunately the iteratee tests aren't exhaustive, but if it builds
> with MTL it should work.  I'm more surprised that it built just by
> changing the .cabal file;

Nope, no hacking required beyond the .cabal file.

> I would expect you'd have to hack up the
> imports in the source code.

Thats actually the problem, MTL and Transformers both provide
Control.Monad.Identity, Control.Monad.Trans and possibly others.

Erik
-- 
--
Erik de Castro Lopo
http://www.mega-nerd.com/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: MTL vs Transformers?

[John Lato]

> From: Erik de Castro Lopo 
>
> Well Iteratee built with MTL passes all the tests that shipped with it
> so I suppose it must be correct.
>

Unfortunately the iteratee tests aren't exhaustive, but if it builds
with MTL it should work.  I'm more surprised that it built just by
changing the .cabal file; I would expect you'd have to hack up the
imports in the source code.

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

[Haskell-cafe] Experiments with defunctionalization, church-encoding and CPS

[Eugene Kirpichov]

I took a toy problem - find the first node satisfying a predicate in a
binary tree, started with a naive Maybe-based implementation - and
experimented with 3 ways of changing the program:
 - Church-encode the Maybe
 - Convert the program into CPS
 - Defunctionalize the Church-encoded or CPS-transformed program
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=10686

The link points to code, a benchmark and conclusion.

Conclusion:
 - Haskell implements Maybe well enough that it is not possible to do better
 - Defunctionalization and consequent optimization yields same
performance as the one with Maybe
 - Non-simplified CPS and Church-encoded representations do bad

-- 
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] MTL vs Transformers?

[Erik de Castro Lopo]

Erik de Castro Lopo wrote:

> However after reading the hackage descriptions of both Transformers and
> MTL, it seems that they share a very similar heritage. I therefore hacked
> the iteratee.cabal file and replaced the build-depends on transformers
> with one on mtl and the package built quite happily. I'll play with it
> a bit to see if its working correctly.

Well Iteratee built with MTL passes all the tests that shipped with it
so I suppose it must be correct.

Erik
-- 
--
Erik de Castro Lopo
http://www.mega-nerd.com/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] MTL vs Transformers?

[Daniel Schüssler]

On Tuesday 13 October 2009 02:46:29 Erik de Castro Lopo wrote:
> Hi all,
> 
> I've just received the following error message:
> 
>   headers.hs:6:7:
> Could not find module `Control.Monad.Identity':
>   it was found in multiple packages: transformers-0.1.4.0 mtl-1.1.0.2
> 
> I'm trying to use the Iteratee module which depends on Transformers
> but I use MTL in other stuff.
> 
> Whats the preferred solution here?
> 
> Erik
> 

Hi,

alternative to ghc-pkg:

{-# LANGUAGE -XPackageImports #-}
module Blub where

import "mtl" Control.Monad.State

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

RE: [Haskell-cafe] Why MTL and Transformers?

[Sittampalam, Ganesh]

Gregory Crosswhite wrote:
> Something that I have been wondering for a while is:  why are there
> *still* two monad transformer libraries with seemingly identical
> functionality, especially given that they have conflicting
> namespaces?  It creates stupid problems like the one that Erik
> encountered and had to work around.   
> 
> I recognize that this situation most likely came about via historical
> accident rather than by intention, but why does it continue to be
> true?  

The intention is to migrate to transformers, which has a slightly better
design and separates out the functional dependencies into a separate
package (monads-fd), thus allowing use of the type families variant
(monads-tf) instead.

This has been discussed to some extent on the libraries list and a
workable strategy involving making a new mtl 2.0 that re-exports
transformers has been suggested. However the migration from extralibs to
the Haskell Platform put the brakes on further progress for a bit.

Now that this migration is essentially complete I have been intending to
revive the proposal but haven't got round to it yet. Please do jump in
and do so yourself if you feel motivated!

Cheers,

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] Type-level naturals & multiplication

[Simon Peyton-Jones]

| > Is there any way to define type-level multiplication without requiring
| > undecidable instances?
| 
| No, not at the moment.  The reasons are explained in the paper "Type
| Checking with Open Type Functions" (ICFP'08):
| 
|http://www.cse.unsw.edu.au/~chak/papers/tc-tfs.pdf
| 
| We want to eventually add closed *type families* to the system (ie,
| families where you can't add new instances in other modules).  For
| such closed families, we should be able to admit more complex
| instances without requiring undecidable instances.

It's also worth noting that while "undecidable" instances sound scary, but all 
it means is that the type checker can't prove that type inference will 
terminate.  We accept this lack-of-guarantee for the programs we *run*, and 
type inference can (worst case) take exponential time which is not so different 
from failing to terminate; so risking non-termination in type inference is 
arguably not so bad.

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

Re: [Haskell-cafe] MTL vs Transformers?

[Ross Paterson]

On Tue, Oct 13, 2009 at 12:08:21PM +1100, Erik de Castro Lopo wrote:
> Here's an example. CGI uses MTL, Iteratee uses Transformers.
> 
> So, how do you use CGI and Iteratee in the same program?

There should be no problem with that, as long as you build your program
using cabal.  Cabal will build each package exposing only the packages
it directly depends on.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] MTL vs Transformers?

[Ross Paterson]

On Tue, Oct 13, 2009 at 08:43:12AM +0100, Ross Paterson wrote:
> On Tue, Oct 13, 2009 at 12:08:21PM +1100, Erik de Castro Lopo wrote:
> > Here's an example. CGI uses MTL, Iteratee uses Transformers.
> > 
> > So, how do you use CGI and Iteratee in the same program?
> 
> There should be no problem with that, as long as you build your program
> using cabal.  Cabal will build each package exposing only the packages
> it directly depends on.

Ah, I see: both packages have MonadIO and MonadTrans in their interface.
That will be a problem, which will only be fixed by the proposed
transition Ganesh mentioned.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] MTL vs Transformers?

[Martijn van Steenbergen]

Erik de Castro Lopo wrote:

However after reading the hackage descriptions of both Transformers and
MTL, it seems that they share a very similar heritage. I therefore hacked
the iteratee.cabal file and replaced the build-depends on transformers
with one on mtl and the package built quite happily. I'll play with it
a bit to see if its working correctly.


I think the standard solutions are
* use Cabal for your project and/or
* use the PackageImports extension.

HTH,

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