Roman Cheplyaka | 8 May 08:46 2013

Mutually recursive modules

I wonder whether it's always possible to break cycles using GHC's
.hs-boot files.

Consider the following schematic example:

  module A where

  import B

  data A

  f :: B -> A
  f = undefined B.g

  module B where

  import A

  data B

  g :: A -> B
  g = undefined A.f

A.hs-boot must give a type signature for f, and since the signature
contains 'B', it must import 'B'. Ditto for B.hs-boot — it must import
'A'.

Even if we treat all imports as {-# SOURCE #-}, there is still a cycle
between the hs-boot files.

(Continue reading)

Francesco Mazzoli | 8 May 09:51 2013
Picon

Re: Mutually recursive modules

At Wed, 8 May 2013 09:46:08 +0300,
Roman Cheplyaka wrote:
> 
> I wonder whether it's always possible to break cycles using GHC's
> .hs-boot files.
> 
> Consider the following schematic example:
> 
>   module A where
> 
>   import B
> 
>   data A
> 
>   f :: B -> A
>   f = undefined B.g
> 
>   module B where
> 
>   import A
> 
>   data B
> 
>   g :: A -> B
>   g = undefined A.f
> 
> A.hs-boot must give a type signature for f, and since the signature
> contains 'B', it must import 'B'. Ditto for B.hs-boot — it must import
> 'A'.
> 
(Continue reading)

Roman Cheplyaka | 8 May 14:22 2013

Re: Mutually recursive modules

Ah yes, thank you!

* Francesco Mazzoli <f <at> mazzo.li> [2013-05-08 08:51:12+0100]
> At Wed, 8 May 2013 09:46:08 +0300,
> Roman Cheplyaka wrote:
> > 
> > I wonder whether it's always possible to break cycles using GHC's
> > .hs-boot files.
> > 
> > Consider the following schematic example:
> > 
> >   module A where
> > 
> >   import B
> > 
> >   data A
> > 
> >   f :: B -> A
> >   f = undefined B.g
> > 
> >   module B where
> > 
> >   import A
> > 
> >   data B
> > 
> >   g :: A -> B
> >   g = undefined A.f
> > 
> > A.hs-boot must give a type signature for f, and since the signature
(Continue reading)

Malcolm Wallace | 24 Sep 14:59 2004
Picon

Re: mutually recursive modules

Henning Thielemann <iakd0 <at> clusterf.urz.uni-halle.de> writes:

> As far as can see neither Hugs or GHC really support them. Is this still
> on the to-do list or is it almost dropped due to implementation
> difficulties? 

Hugs doesn't support mutually-recursive modules at all.  Ghc and nhc98
support them only if you hand-write a .hi-boot file to bootstrap the
compilation.  I would guess that better support from the mainstream
implementations is unlikely, because it would be a large amount of
effort for a situation which occurs only very rarely, and for which
there is a relatively easy workaround.

Some lesser-known Haskell implementations do fully support
mutually-recursive modules however.  hhc (formerly Freja, from
Henrik Nilsson) allows multiple modules to be stored in a single
file, and hence mutual recursion can be achieved by ensuring all the
recursive modules are compiled simultaneously from the same file.
The PacSoft Haskell system (from the Programatica project at OGI)
also fully supports mutually recursive modules, and I believe they
can even be in separate files.

Regards,
    Malcolm
Chris Kuklewicz | 15 Jul 13:21 2008

Mutually recursive modules and google protocol-buffers

I have reached an impasse in designing a Haskell API for the google's
protocol-buffers data language / format. (
http://code.google.com/apis/protocolbuffers/docs/overview.html )

The messages in protobuf are defined in a namespace that nests in the usual
hierarchical OO style that Java encourages.

To avoid namespace conflicts, I made a hierarchy of modules.

But...this is a legal pair protobuf message definitions:

> // Test that mutual recursion works.
> message TestMutualRecursionA {
>   optional TestMutualRecursionB b = 1;
>   optional int32 content = 2;
> }
> 
> message TestMutualRecursionB {
>   optional TestMutualRecursionA a = 1;
>   optional int32 content = 2;
> }

And there is no way ghc can compile these in separate modules.

But the overlap of record accessors names "content" makes defining these
messages in a single module with a common namespace quite verbose.

Any opinions on the least worst way to design this?

--

-- 
(Continue reading)

Max Bolingbroke | 15 Jul 15:20 2008
Picon

Re: Mutually recursive modules and google protocol-buffers

> And there is no way ghc can compile these in separate modules.

I may be being redundant here, but you may not know that GHC actually
can compile mutually recursive modules. See
http://www.haskell.org/ghc/docs/latest/html/users_guide/separate-compilation.html#mutual-recursion
. Of course, this is not a great solution either, as creating hs-boot
files is a bit tedious, but at least the option is there.

Cheers,
Max
Chris Kuklewicz | 15 Jul 16:43 2008

Re: Mutually recursive modules and google protocol-buffers

Ah, a teachable moment.  One of us is not entirely correct about what GHC can do 
with this example.  Hopefully I am wrong, but my experiments...

Max Bolingbroke wrote:
>> And there is no way ghc can compile these in separate modules.
> 
> I may be being redundant here, but you may not know that GHC actually
> can compile mutually recursive modules. See
> http://www.haskell.org/ghc/docs/latest/html/users_guide/separate-compilation.html#mutual-recursion
> . Of course, this is not a great solution either, as creating hs-boot
> files is a bit tedious, but at least the option is there.
> 
> Cheers,
> Max

Consider these 3 files:

A.hs:
> module A(A) where
> import B(B)
> data A = A B

B.hs
> module B(B) where
> import A(A)
> data B = B A

Main.hs
 > module Main where
 > import A
(Continue reading)

Henning Thielemann | 15 Jul 16:54 2008
Picon

Re: Mutually recursive modules and google protocol-buffers


On Tue, 15 Jul 2008, Chris Kuklewicz wrote:

> Consider these 3 files:
>
> A.hs:
>> module A(A) where
>> import B(B)
>> data A = A B
>
> B.hs
>> module B(B) where
>> import A(A)
>> data B = B A
>
> Main.hs
>> module Main where
>> import A
>> import B
>> main = return ()

Sooner or later you want generalize your datatypes. Then you can define
    data A b = A b
   and you do not need to import B any longer. I do not know if this is a 
generally applicable approach, but it helped me in some cases.
  There is still a problem with mutually recursive classes. In the one case 
where I had this problem, I could solve it the opposite way, namely by 
turning one type variable into a concrete type, which could represent all 
values one could represent with the variable type.
(Continue reading)

Stuart Cook | 15 Jul 17:36 2008
Picon

Re: Mutually recursive modules and google protocol-buffers

On Wed, Jul 16, 2008 at 12:54 AM, Henning Thielemann
<lemming <at> henning-thielemann.de> wrote:
> Sooner or later you want generalize your datatypes. Then you can define
>   data A b = A b
>  and you do not need to import B any longer. I do not know if this is a
> generally applicable approach, but it helped me in some cases.

This only really works if it's "natural" for A to be polymorphic in b.
Otherwise you end up with all sorts of irrelevant administrative type
parameters polluting your signatures.

(I recently had a similar problem with mutually recursive modules; I
ended up deciding to write my program in not-Haskell instead, which
made me a little sad.)

Stuart
Roberto Zunino | 15 Jul 17:10 2008
Picon
Picon

Re: Mutually recursive modules and google protocol-buffers

Chris Kuklewicz wrote:
> There is no way to create a "A.hs-boot" file that has all of
>   (1) Allows A.hs-boot to be compiled without compiling B.hs first
>   (2) Allows B.hs (with a {-# SOURCE #-} pragma) to be compiled after 
> A.hs-boot
>   (3) Allows A.hs to compiled after A.hs-boot with a consistent interface

I thought the following A.hs-boot would suffice:

module A(A) where
data A

There's no need to provide the data constructors for type A. Does this 
violate any of the goals above?

Regards,
Zun.
Chris Kuklewicz | 16 Jul 12:01 2008

Re: [Haskell-cafe] Mutually recursive modules and google protocol-buffers

Thanks Roberto!

Roberto Zunino wrote:
> Chris Kuklewicz wrote:
>> There is no way to create a "A.hs-boot" file that has all of
>>   (1) Allows A.hs-boot to be compiled without compiling B.hs first
>>   (2) Allows B.hs (with a {-# SOURCE #-} pragma) to be compiled after 
>> A.hs-boot
>>   (3) Allows A.hs to compiled after A.hs-boot with a consistent interface
> 
> I thought the following A.hs-boot would suffice:
> 
> module A(A) where
> data A
> 
> There's no need to provide the data constructors for type A. Does this 
> violate any of the goals above?
> 
> Regards,
> Zun.

I tried that experiment.  The failure is complicated, and triggers be a ghc bug.

Hmmm... the bug for

> module A(A) where
> data A
>   deriving Show

using "ghc -c -XGeneralizedNewtypeDeriving A.hs-boot" is
(Continue reading)

Sittampalam, Ganesh | 16 Jul 13:03 2008

RE: [Haskell-cafe] Mutually recursive modules and google protocol-buffers

Hi,

> module A(A) where
> data A
>   deriving Show

I think you should use "instance Show A" rather than "deriving Show".
All the boot file needs to do is say that the instance exists, not
explain how it is constructed.

Cheers,

Ganesh

==============================================================================
Please access the attached hyperlink for an important electronic communications disclaimer: 

http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html
==============================================================================
Sterling Clover | 15 Jul 17:12 2008
Picon

Re: Mutually recursive modules and google protocol-buffers

What about generating the verbose accessor/single module code, and  
then creating a hierarchical module space as well, all importing your  
Base module, and reexporting the data types you want as well as less  
verbosely named accessor functions? Of course, this will break record  
update syntax, but maybe you could move to functional references  
instead -- given that you're generating all the code to begin with,  
autogenerating fref/lens style getter-setter pairs shouldn't be any  
more work.

--Sterl

On Jul 15, 2008, at 10:43 AM, Chris Kuklewicz wrote:

> Ah, a teachable moment.  One of us is not entirely correct about  
> what GHC can do with this example.  Hopefully I am wrong, but my  
> experiments...
>
> Max Bolingbroke wrote:
>>> And there is no way ghc can compile these in separate modules.
>> I may be being redundant here, but you may not know that GHC actually
>> can compile mutually recursive modules. See
>> http://www.haskell.org/ghc/docs/latest/html/users_guide/separate- 
>> compilation.html#mutual-recursion
>> . Of course, this is not a great solution either, as creating hs-boot
>> files is a bit tedious, but at least the option is there.
>> Cheers,
>> Max
>
> Consider these 3 files:
>
(Continue reading)

John Meacham | 15 Jul 23:34 2008
Picon

Re: Mutually recursive modules and google protocol-buffers

On Tue, Jul 15, 2008 at 12:21:16PM +0100, Chris Kuklewicz wrote:
> I have reached an impasse in designing a Haskell API for the google's
> The messages in protobuf are defined in a namespace that nests in the usual
> hierarchical OO style that Java encourages.
>
> To avoid namespace conflicts, I made a hierarchy of modules.

I wonder if this is the root of your issue, OO concepts don't map
directly to haskell concepts a lot of the time. You may end up with some
very atypical haskell code if you try to copy OO designs directly. 

        John 

--

-- 
John Meacham - ⑆repetae.net⑆john⑈
Jason Dusek | 16 Jul 02:29 2008
Picon

Re: Mutually recursive modules and google protocol-buffers

John Meacham <john <at> repetae.net> wrote:
> Chris Kuklewicz wrote:
> > I have reached an impasse in designing a Haskell API for the
> > google's The messages in protobuf are defined in a namespace
> > that nests in the usual hierarchical OO style that Java
> > encourages.
>
> > To avoid namespace conflicts, I made a hierarchy of modules.
>
> I wonder if this is the root of your issue, OO concepts don't
> map directly to haskell concepts a lot of the time. You may
> end up with some very atypical haskell code if you try to copy
> OO designs directly.

  What do you think is a good approach to a protocol buffer
  parser generator?

--

-- 
_jsn

Gmane