Re: [Haskell-cafe] Variants of a recursive data structure
Hello, I have had similar difficulties. My first approach (for my AST) was to use indirect composite. You seem to have the beginnings of that. However it would require a custom newtype for each AST form: data Exp e = Num Int | Add e e newtype SimpleExp = Exp SimpleExp newtype LabeledExp = Labelled (Exp LabeledExp) For my reduced AST, however, I switched to a different principle. I combined the idea of tagging with the concepts of GADTs and this worked quite succesfully. It even makes it very easy to remove any tagging: data Exp_; data Exp :: * - * Num :: Int - Exp a Exp :: Exp a - Exp a - Exp a Tag :: a - Exp a - Exp a I have combined this with bringert's GADT paper and that worked quite successfully. (However in my case it is a GADT with two parameters as I don't only have Exp's, so it would look more like this: data Exp_; data Var_; data Value_; data Exp :: * - * - * where VDef :: String - Exp Var_ tag VVar :: Exp Var_ tag - Exp Value_ tag EValue :: Exp Value_ tag - Exp Exp_ tag EAdd :: Exp Exp_ tag - Exp Exp_ tag - Exp Exp_ tag Tag:: tag - Exp a tag - Exp a tag ) Hope this helps, Cheers Klaus Ostermann wrote: Hi all, I have a problem which is probably not a problem at all for Haskell experts, but I am struggling with it nevertheless. I want to model the following situation. I have ASTs for a language in two variatns: A simple form and a labelled form, e.g. data SimpleExp = Num Int | Add SimpleExp SimpleExp data LabelledExp = LNum Int String | LAdd LabelledExp LabelledExp String I wonder what would be the best way to model this situation without repeating the structure of the AST. I tried it using a fixed point operator for types like this: data Exp e = Num Int | Add e e data Labelled a = L String a newtype Mu f = Mu (f (Mu f)) type SimpleExp = Mu Exp type LabelledExp = Mu Labelled Exp The SimpleExp definition works fine, but the LabeledExp definition doesn't because I would need something like Mu (\a - Labeled (Exp a)) where \ is a type-level lambda. However, I don't know how to do this in Haskell. I'd need something like the . operator on the type-level. I also wonder whether it is possible to curry type constructors. The icing on the cake would be if it would also be possible to have a function unlabel :: LabeledExp - Exp that does *not* need to know about the full structure of expressions. So, what options do I have to address this problem in Haskell? Klaus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Christophe Poucet Ph.D. Student DESICS - DDT Phone:+32 16 28 87 20 E-mail: Christophe (dot) Poucet (at) imec (dot) be IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – http://www.imec.be IMEC e-mail disclaimer: http://www.imec.be/wwwinter/email-disclaimer.shtml ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] seq - RTFM?
Hello Dusan, The reason why that does not work as you expect it to is because the type of the whole expression is not monadic. Therefore it will basically evaluate the action until it's an action ready to be executed, but not execute it, cause it's not in the IO monad. It's the same as having a list of [putStr a, putStr b]. Until you start placing these actions in the IO monad, they'll just be values. Hope that's somewhat clear Dusan Kolar wrote: Hello all, my question is probably dull. So answers to better investigate manual are welcome. Why is this correct? ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.4.1, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \/\/ /_/\/|_| Type :? for help. Loading package base-1.0 ... linking ... done. Prelude putStr Ahoj\n Ahoj Prelude putStr Ahoj\n `seq` 3+3 6 Prelude :q Leaving GHCi. And not Prelude putStr Ahoj\n Ahoj Prelude putStr Ahoj\n `seq` 3+3 Ahoj 6 ??? Does it have something common with monads or is it a behavior of seq? Thanks, Dusan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Christophe Poucet Ph.D. Student DESICS - DDT Phone:+32 16 28 87 20 E-mail: Christophe (dot) Poucet (at) imec (dot) be IMEC vzw -- Register of Legal Entities Leuven VAT BE 0425.260.668 -- Kapeldreef 75, B-3001 Leuven, Belgium -- http://www.imec.be IMEC e-mail disclaimer: http://www.imec.be/wwwinter/email-disclaimer.shtml ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Cyclic Type-synonyms
Hello,
I use the Indirect Composite pattern a lot, and this means that
typically, especially with recursive types (such as an AST), you end up
with a lot of data-constructors. I understand that it is not
possible to have pure cyclic types (because haskell requires
iso-recursive and not equi-recursive types). However I wonder why
certain cases can not be allowed.
For instance, assume the following somewhat simplified AST:
data Exp e =
ELet String e e -- let x = a in b
| ECond e e e -- If then else construct
Now if I wanted to decorate this structure, I would use something like:
data AnnotExp a = AE {
unAE :: Exp (AnnotExp a),
note :: a
}
However, and this
example might be slightly too trivial to motivate it, however it does
exemplify what can be done, one might not want to annotate at all and
just have a recursive data AST. At this point, one either uses
AnnotExp () or creates a new data type. It would be nice if
instead one could use cyclic type-declarations, with the knowledge that
we're going through a data-constructor and hence the type iso-recursive
and not equi-recursive:
type AST = Exp AST -- This is iso-recursive as it goes through the data constructors ELet and ECond
Sadly this is not
possible with the current GHC (I'm using 6..4.2). Is this
possible with 6.6? Is there any reason why this is not
possible. Feedback regarding this is welcome. A more
motivating example can be seen below.
Cheers,
Christophe
-
data Exp var ident func exp stm =
ELit
Lit
-- ^ Literals
| EVar ident -- ^ Identifiers
| EData Const [exp] -- ^ Data Constructors
| ECall func -- ^ Function Calls
| ELet var stm stm -- ^ Scoping
| ECond exp stm stm -- ^ Conditional
| ELoop exp stm -- ^ Looping
deriving (Eq, Show)
data AExp exp annot = AExp {
unAExp :: exp,
aexpNote :: annot,
aexpLoc :: Location
}
type UnCorExp var annot =
Exp
var
-- ^ Let-binders
var
-- ^ Named identifiers
(Ident, [AExp UnCorExp var annot]) -- ^ Function calls
(AExp UnCorExp var
annot)
-- ^ Expressions
(AExp UnCorExp var
annot)
-- ^ Statements
-- Flattened AST: function parameters can only be variables, similar for while- and if- conditions
type UnSimExp var annot
Exp
var
-- ^ Let-binders
var
-- ^ Named identifiers
(Ident,
[var])
-- ^ Function calls
(var)
-- ^ Expressions
(AExp UnSimExp var
annot)
-- ^ Statements
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Cyclic Type-synonyms
Addendum:
(18:19:50) vincenz: anyways the haskell-cafe post is orthogonal to this safety issue
(18:20:46) vincenz:
it's about the inability to use a generic annotation data-type with any
generic indirect composite ADT without introducing a third data
constructor if one wants recursion
(18:21:33) vincenz: data Foo a = A a; date Note a n = Note { data :: a, info :: n} ;type RecNoteFoo = Note (Foo RecNoteFoo) Int
(18:25:53) audreyt: vincenz: that is a good summary.
(18:26:17) audreyt: sugar selectors, smart constructors, SYB, etc.
(18:26:24) audreyt: but the core problem seems like a real limitation
On 7/5/06, Christophe Poucet [EMAIL PROTECTED] wrote:
Hello,
I use the Indirect Composite pattern a lot, and this means that
typically, especially with recursive types (such as an AST), you end up
with a lot of data-constructors. I understand that it is not
possible to have pure cyclic types (because haskell requires
iso-recursive and not equi-recursive types). However I wonder why
certain cases can not be allowed.
For instance, assume the following somewhat simplified AST:
data Exp e =
ELet String e e -- let x = a in b
| ECond e e e -- If then else construct
Now if I wanted to decorate this structure, I would use something like:
data AnnotExp a = AE {
unAE :: Exp (AnnotExp a),
note :: a
}
However, and this
example might be slightly too trivial to motivate it, however it does
exemplify what can be done, one might not want to annotate at all and
just have a recursive data AST. At this point, one either uses
AnnotExp () or creates a new data type. It would be nice if
instead one could use cyclic type-declarations, with the knowledge that
we're going through a data-constructor and hence the type iso-recursive
and not equi-recursive:
type AST = Exp AST -- This is iso-recursive as it goes through the data constructors ELet and ECond
Sadly this is not
possible with the current GHC (I'm using 6..4.2). Is this
possible with 6.6? Is there any reason why this is not
possible. Feedback regarding this is welcome. A more
motivating example can be seen below.
Cheers,
Christophe
-
data Exp var ident func exp stm =
ELit
Lit
-- ^ Literals
| EVar ident -- ^ Identifiers
| EData Const [exp] -- ^ Data Constructors
| ECall func -- ^ Function Calls
| ELet var stm stm -- ^ Scoping
| ECond exp stm stm -- ^ Conditional
| ELoop exp stm -- ^ Looping
deriving (Eq, Show)
data AExp exp annot = AExp {
unAExp :: exp,
aexpNote :: annot,
aexpLoc :: Location
}
type UnCorExp var annot =
Exp
var
-- ^ Let-binders
var
-- ^ Named identifiers
(Ident, [AExp UnCorExp var annot]) -- ^ Function calls
(AExp UnCorExp var
annot)
-- ^ Expressions
(AExp UnCorExp var
annot)
-- ^ Statements
-- Flattened AST: function parameters can only be variables, similar for while- and if- conditions
type UnSimExp var annot
Exp
var
-- ^ Let-binders
var
-- ^ Named identifiers
(Ident,
[var])
-- ^ Function calls
(var)
-- ^ Expressions
(AExp UnSimExp var
annot)
-- ^ Statements
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Darcs-synchronisation tool
Hello,I typically back up my darcs repositories on different computers. However I do always use the same structure for the different forests of darcs repositories. Lately my laptop charger has died which has led me to constantly use a usbstick to move these repositories. Therefore I have started working on a little tool that will automatically sychronise similarly laid out darcs-forests. At the moment it's very bare-to-the-bones. IT will only darcs pull from the repositories in one forest to the other. I later plan to add options to automatically darcs init when necessary (another thing which I've personally missed from time to time). So, if you find yourself in a similar situation, or you have thoughts, concerns, comments regarding it, feedback is welcome!The source can be found at http://www.notvincenz.com/wiki/uploads/Personal/ApplyDarcs.hs and requires Neil Mitchell's http://www.cs.york.ac.uk/fp/darcs/filepath/System/FilePath.hs renamed as plain FilePath.hs. Cheers,Christophe (vincenz) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Scoped data declarations
Hello,Well one specific example where this would be useful is for lambdabot and similar systems. Additionally this could be useful for experimenting in any interpreter such as hugs or ghci.Regards On 6/26/06, Sebastian Sylvan [EMAIL PROTECTED] wrote: On 6/23/06, Christophe Poucet [EMAIL PROTECTED] wrote: Dear, Yesterday, while discussing with Cale and SamB on I suddenly came up with the crazy idea of scoped data declarations.After some brief discussion to check the validity, I finally came to the conclusion that they should be feasible. In addition, I don't think that they would require a high amount of changes in current compilers. Basically if you have something like: module Main where foo = let data Foo = Foo deriving Show in Foo\ main :: IO () main = print foo One can see this as having an extra hidden module that defines Foo but that does not export it.The only change that is then required is that while compiling Foo, the hidden-ness of Foo must be removed. For instance, if one were to load this into, say, ghci (this is fictive of course): # ghci Main.hs :t foo foo :: Codeloc2.Foo There were initially some objections to this, because it is no longer feasible to actually write the type of the function foo.But if one looks at current GHC, this objection is already there: module A(foo) where data Foo = Foo deriving Show foo = Foo module Main where import A main = print foo As Excedrin then pointed out, importing this Main into ghci, gives foo :: Foo.Foo And this notation can not be written in Main either, because Foo is hidden in A. Therefore, I would like to note that scoped data declarations are just like hidden data-declarations with two extra requirements: 1) Generate source-location-based submodule names 2) Add an extra import rule for those hidden modules in the subexpressions of where the data-declaration is being originally defined. Comments are welcome, of course :)I'm not sure I understand why this is something we need. Do you have any examples where this would be useful?/S--Sebastian Sylvan+46(0)736-818655UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Scoped data declarations
Dear,Yesterday, while discussing with Cale and SamB on I suddenly came up with the crazy idea of scoped data declarations. After some brief discussion to check the validity, I finally came to the conclusion that they should be feasible. In addition, I don't think that they would require a high amount of changes in current compilers. Basically if you have something like:module Main wherefoo = let data Foo = Foo deriving Show in Foo\main :: IO ()main = print fooOne can see this as having an extra hidden module that defines Foo but that does not export it. The only change that is then required is that while compiling Foo, the hidden-ness of Foo must be removed. For instance, if one were to load this into, say, ghci (this is fictive of course):# ghci Main.hs :t foofoo :: Codeloc2.FooThere were initially some objections to this, because it is no longer feasible to actually write the type of the function foo. But if one looks at current GHC, this objection is already there: module A(foo) wheredata Foo = Foo deriving Showfoo = Foomodule Main whereimport Amain = print fooAs Excedrin then pointed out, importing this Main into ghci, givesfoo :: Foo.Foo And this notation can not be written in Main either, because Foo is hidden in A.Therefore, I would like to note that scoped data declarations are just like hidden data-declarations with two extra requirements: 1) Generate source-location-based submodule names2) Add an extra import rule for those hidden modules in the subexpressions of where the data-declaration is being originally defined.Comments are welcome, of course :) Cheers!Christophe (vincenz) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type class hell
I'm not certain but I think this will still fail for exactly the piece that you ignored, which is the crux of the problem.On 6/8/06, Greg Buchholz
[EMAIL PROTECTED] wrote:
Christophe Poucet wrote: The idea however is that MonoType is going to be used in a recursive way. For instance: newtype FMT = FMT MonoType FMT instance FMT where...
Er, I'll ignore this part. And this definition will have to reside on recursive definitions. In the style of how HasVars was instantiated: instance HasVars a = HasVars (MonoType a) where
freeVars (TyVar x) = [x] freeVars (TyConst _ xs) = nub . concatMap freeVars $ xs occurs x (TyVar y) = x == y occurs x (TyConst _ xs) = or . map (occurs x) $ xs So for Type
instance Type a = Type (MonoType a) where ... That's where it becomes rather troublesome.Yeah, after a certain point of complexity with type classes, itstarts to look like C++ templates.How about something like...
{-# OPTIONS -fglasgow-exts #-}{-# OPTIONS -fallow-undecidable-instances #-}import Listtype Var = Stringtype Const = Stringdata MonoType mt = TyVar Var | TyConst Const [mt] deriving (Eq, Show)
data PolyType mt = TyPoly [Var] mt deriving (Show)class Type a b wheretoType :: b - a bfromType :: a b - bfreeVars :: a b - [Var]occurs :: Var - a b - Bool
data Nil = Nilinstance Type MonoType Nil wherefreeVars (TyVar x) = [x]freeVars (TyConst _ xs) = [???]instance (Type a b) = Type MonoType (a b) wherefreeVars (TyVar x) = [x]
freeVars (TyConst _ xs) = nub . concatMap freeVars $ xsoccurs x (TyVar y) = x == yoccurs x (TyConst _ xs) = or . map (occurs x) $ xsmain = print $ freeVars $TyConst foo [TyConst bar[Nil],
TyConst baz[Nil], TyVar quux]___Haskell-Cafe mailing list
Haskell-Cafe@haskell.orghttp://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] Undecideable instances for one instance?
Dear,
Recently I was wrapping something in a typeclass (you may argue the
reason for the typeclass, I will admit that's no longer needed, yet the
compile error still begs questioning). Basically if you have only one
global instance of a typeclass (so there is no overlapping), GHC will
still complain about overlapping. Is there any reason this is so or is
this a remnant of more complicated overlapping situations?
The sample code is:
{-# OPTIONS_GHC -fglasgow-exts #-}
module Main where
data Located a = L a
class Locatable a where
value :: Located a - a
wrap :: a - Located a
instance Locatable a where
value (L a) = a
wrap a = L a
main :: IO ()
main = do
print . value . wrap $ 1
-- Illegal instance declaration for `Locatable a'
-- (There must be at least one non-type-variable in the instance head
-- Use -fallow-undecidable-instances to permit this)
-- In the instance declaration for `Locatable a'
Christophe(vincenz)
--
Christophe Poucet
Ph.D. Student
Phone:+32 16 28 87 20
E-mail: Christophe (dot) Poucet (at) imec (dot) be
Website: http://notvincenz.com/
IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be
*DISCLAIMER*
This e-mail and/or its attachments may contain confidential information. It is
intended solely for the intended addressee(s).
Any use of the information contained herein by other persons is prohibited.
IMEC vzw does not accept any liability for the contents of this e-mail and/or
its attachments.
**
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Fwd: [Haskell-cafe] Undecideable instances for one instance?
Hello Bulat,You are indeed correct. However I fail to see how there is any undecideability. If instead one specified it as follows, it would be fine:class Locatable a b | a - b, b - a where value :: a - b wrap :: b - ainstance Locatatable (Located a) a where value (L a) = a wrap a = L aIt compiles fine, yet this is semantically the same. On 6/7/06, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Christophe,Wednesday, June 7, 2006, 12:27:22 PM, you wrote: global instance of a typeclass (so there is no overlapping), GHC will still complain about overlapping. Is there any reason this is so or is GHC compains here about undecidability, not overlapping :) -- Illegal instance declaration for `Locatable a' -- (There must be at least one non-type-variable in the instance head -- Use -fallow-undecidable-instances to permit this) -- In the instance declaration for `Locatable a' Christophe(vincenz)--Best regards, Bulatmailto: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Type class hell
Dear, I am writing a compiler (as you may have gathered from some previous messages). Anyways I am stuck with a small monadic issue. I mostly use indirect composite as this gives me the most flexibility with regards taking out parts of the AST, or decorating at whim. Basically the question regards how to implement a certain instance. Currently I have the code that can be seen below. What I would like to do is combine HasVars and Type (mostly because in my framework the two concepts shouldn't be divided from a design perspective) into one type class to clean it up a bit. However I fail to see how I would implement toType and fromType for the given instance. Is this feasible without resorting to ugly hacks? --- Types data MonoType mt = TyVar Var | TyConst Const [mt] deriving (Eq, Show) data PolyType mt = TyPoly [Var] mt deriving (Show) class Type mt where toType :: mt - MonoType mt fromType :: MonoType mt - mt class HasVars a where freeVars :: a - [Var] occurs :: Var - a - Bool toPoly :: (HasVars a) = a - PolyType a toPoly x = TyPoly (freeVars x) x instance HasVars a = HasVars (MonoType a) where freeVars (TyVar x) = [x] freeVars (TyConst _ xs) = nub . concatMap freeVars $ xs occurs x (TyVar y) = x == y occurs x (TyConst _ xs) = or . map (occurs x) $ xs Cheers, Christophe(vincenz) -- Christophe Poucet Ph.D. Student Phone:+32 16 28 87 20 E-mail: Christophe (dot) Poucet (at) imec (dot) be Website: http://notvincenz.com/ IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be *DISCLAIMER* This e-mail and/or its attachments may contain confidential information. It is intended solely for the intended addressee(s). Any use of the information contained herein by other persons is prohibited. IMEC vzw does not accept any liability for the contents of this e-mail and/or its attachments. ** ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type class hell
Hello Greg,
The idea however is that MonoType is going to be used in a recursive
way. For instance:
newtype FMT = FMT MonoType FMT
instance FMT where...
And this definition will have to reside on recursive definitions. In the
style of how HasVars was instantiated:
instance HasVars a = HasVars (MonoType a) where
freeVars (TyVar x) = [x]
freeVars (TyConst _ xs) = nub . concatMap freeVars $ xs
occurs x (TyVar y) = x == y
occurs x (TyConst _ xs) = or . map (occurs x) $ xs
So for Type
instance Type a = Type (MonoType a) where
...
That's where it becomes rather troublesome.
Greg Buchholz wrote:
Christophe Poucet wrote:
What I would like to do is combine HasVars and Type (mostly because in my
framework the two concepts shouldn't be divided from a design perspective)
into one type class to clean it up a bit. However I fail to see how I would
implement toType and fromType for the given instance. Is this feasible
without resorting to ugly hacks?
{-# OPTIONS -fglasgow-exts #-}
-- Multiparameter type classes?
import List
type Var = String
type Const = String
data MonoType mt = TyVar Var
| TyConst Const [mt] deriving (Eq, Show)
data PolyType mt = TyPoly [Var] mt deriving (Show)
class Type a b where
toType :: b - a b
fromType :: a b - b
freeVars :: a b - [Var]
occurs :: Var - a b - Bool
instance Type MonoType Int
-- yada, yada, yada...
instance Type MonoType (MonoType Int) where
freeVars (TyVar x) = [x]
freeVars (TyConst _ xs) = nub . concatMap freeVars $ xs
occurs x (TyVar y) = x == y
occurs x (TyConst _ xs) = or . map (occurs x) $ xs
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Christophe Poucet
Ph.D. Student
Phone:+32 16 28 87 20
E-mail: Christophe (dot) Poucet (at) imec (dot) be
Website: http://notvincenz.com/
IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be
*DISCLAIMER*
This e-mail and/or its attachments may contain confidential information. It is
intended solely for the intended addressee(s).
Any use of the information contained herein by other persons is prohibited.
IMEC vzw does not accept any liability for the contents of this e-mail and/or
its attachments.
**
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Bug in Data.Graph
Dear, I think I have discovered a bug in Data.Graph. If one looks at the documentation it states: Vertex = (Node, Node) An edge from the first vertex to the second. Ergo (i,j) = j is reachable from i Then continuing, one reads that: topSort :: Graph - [Vertex] A topological sort of the graph. The order is partially specified by the condition that a vertex /i/ precedes /j/ whenever /j/ is reachable from /i/ but not vice versa. However if one tries to evaluate it, one gets: print . G.components $ G.buildG (1,4) [(1,2), (1,3), (2,4), (2,3)] [1,3,2,4] According to specification we have the graph (with arrows pointing down) 1 / \ | 3 |/ 2 | 4 Therefore one would expect [4,2,3,1]. Is this a bug in the documentation or the implementation? With regards, Christophe -- Christophe Poucet Ph.D. Student Phone:+32 16 28 87 20 E-mail: Christophe (dot) Poucet (at) imec (dot) be Website: http://notvincenz.com/ IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be *DISCLAIMER* This e-mail and/or its attachments may contain confidential information. It is intended solely for the intended addressee(s). Any use of the information contained herein by other persons is prohibited. IMEC vzw does not accept any liability for the contents of this e-mail and/or its attachments. ** ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Bug in Data.Graph
I just realized that I was looking at dependencies the wrong way (which is where I'm using this). So please ignore, the implementation is correct, I just made a mental typo :/ Christophe Poucet wrote: Dear, I think I have discovered a bug in Data.Graph. If one looks at the documentation it states: Vertex = (Node, Node) An edge from the first vertex to the second. Ergo (i,j) = j is reachable from i Then continuing, one reads that: topSort :: Graph - [Vertex] A topological sort of the graph. The order is partially specified by the condition that a vertex /i/ precedes /j/ whenever /j/ is reachable from /i/ but not vice versa. However if one tries to evaluate it, one gets: print . G.components $ G.buildG (1,4) [(1,2), (1,3), (2,4), (2,3)] [1,3,2,4] According to specification we have the graph (with arrows pointing down) 1 / \ | 3 |/ 2 | 4 Therefore one would expect [4,2,3,1]. Is this a bug in the documentation or the implementation? With regards, Christophe -- Christophe Poucet Ph.D. Student Phone:+32 16 28 87 20 E-mail: Christophe (dot) Poucet (at) imec (dot) be Website: http://notvincenz.com/ IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be *DISCLAIMER* This e-mail and/or its attachments may contain confidential information. It is intended solely for the intended addressee(s). Any use of the information contained herein by other persons is prohibited. IMEC vzw does not accept any liability for the contents of this e-mail and/or its attachments. ** ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Filtering on data constructors with TH
Dear,
After having read Bulat's mail regarding TH when I had mentioned my wish
for Pretty, I decided to use TH for a much smaller project. That's why
today I have created an automated derivation for data constructor
filtering. As I started coding someone mentioned that something similar
can be done with list comprehensions, so I'm not certain about the scope
of usefulness, however personally I have found the need for this at
times. Anyways, the code can be obtained from the darcs repo at
http://oasis.yi.org:8080/repos/haskell/filter
Suggestions, bugs, additions are always welcome :)
Here is an example:
{-# OPTIONS_GHC -fglasgow-exts -fth #-}
module Main where
import Filter
data T = A Int String | B Integer | C deriving Show
data Plop a b = Foo a | Bar b deriving Show
$(deriveFilter ''T)
$(deriveFilter ''Plop)
main :: IO ()
main = do
let l = [A 1 s, B 2, C]
let l2 = [Foo 1, Bar a, Foo 2, Bar b]
print l
print $ filter isA l
print l2
print $ filter isFoo l2
Cheers
Christophe ([EMAIL PROTECTED])
--
Christophe Poucet
Ph.D. Student
Phone:+32 16 28 87 20
E-mail: Christophe (dot) Poucet (at) imec (dot) be
Website: http://notvincenz.com/
IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be
*DISCLAIMER*
This e-mail and/or its attachments may contain confidential information. It is
intended solely for the intended addressee(s).
Any use of the information contained herein by other persons is prohibited.
IMEC vzw does not accept any liability for the contents of this e-mail and/or
its attachments.
**
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] (no subject)
Dear,
I will try to explain what I'm trying to achieve, below you can find the
code demonstrating where I'm at currently, and where I would like to
ideally get, as well as the current compilation error.
Basically I'm working on a minilanguage that I would like to simulate.
This language is based on a core concept which can in the example below
is Foo. Now there is a 'primitive' instance of Foo that is the list.
What I now want to do is make FooF an instance as well. FooF being a
record based on a map that contains some other instances of Foo by name
as well as code that will use this lookup table.
For instance (this is not definite syntax):
my pseudoproglanguage:
A = [1..10] (aka refer to the 'primitive' instance of Foo)
B = [1..10] (aka refer to the 'primitive' instance of Foo)
bar C = if dum B then bar A else bar B
dum C = dum A dum B
I realize I need existentials for this, but I'm afraid that my type-fu
is lacking in this area. Perhaps one of you could point me in the right
direction.
With regards,
Christophe
{-# OPTIONS_GHC -fglasgow-exts #-}
module FooBar where
import qualified Data.Map as M
class Foo f b | f - b where
foo :: f a - b
bar :: f a - b - b
dum :: f a - b - Bool
instance Foo [] Int where
foo c = 0
bar c i = i+1
dum c i = (length c == i)
data F b a = forall f. Foo f b = F (f a)
instance Foo (F b) b where
foo (F c) = F . foo $ c
bar (F c) i = bar c i
dum (F c) i = dum c i
data FooF b a = FooF {
cols :: M.Map String (F b a),
barC :: M.Map String (F b a) - b - b,
dumC :: M.Map String (F b a) - b - Bool
}
instance Foo (FooF b) b where
foo c = fmap (foo) c
bar c i = barC c (cols c) i
dum c i = dumC c (cols c) i
makeFooF cols barC dumC = FooF {cols = cols, barC = barC, dumC = dumC}
-- Example:
-- makeFooF
-- [(A, [1..10]), (B, [1..8])]
-- (\t - if dum (M.lookup A t)
-- then bar (M.lookup B t)
-- else bar (M.lookup A t)
-- (\t - dum (M.lookup A t) dum (M.lookup B t)
-- Ideally this system would also allow to make some FooF that is based
on another FooF, hence the reason for existentials
-- FooBar.hs:19:16:
-- Couldn't match the rigid variable `b' against `F b1 a'
-- `b' is bound by the instance declaration at FooBar.hs:18:0
-- Expected type: b
-- Inferred type: F b1 a
-- In the _expression_: (F . foo) $ c
-- In the definition of `foo': foo (F c) = (F . foo) $ c
FooBar.hs:31:12:
-- Couldn't match the rigid variable `b' against `f b1'
-- `b' is bound by the instance declaration at FooBar.hs:30:0
-- Expected type: b
-- Inferred type: f b1
-- In the application `fmap (foo) c'
-- In the definition of `foo': foo c = fmap (foo) c
-- Failed, modules loaded: none.
---
--Christophe Poucet
Ph.D. Student
Phone:+32 16 28 87 20
E-mail: Christophe (dot) Poucet (at) imec (dot) be
Website: http://notvincenz.com/
IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be
*DISCLAIMER*
This e-mail and/or its attachments may contain confidential information. It is intended solely for the intended addressee(s).
Any use of the information contained herein by other persons is
prohibited. IMEC vzw does not accept any liability for the contents of
this e-mail and/or its attachments.
**
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] GHC wish
Dear all, I recently stumbled upon something that I think should be added to the GHC wishlist. Not knowing where to put it, I will put it here. As there is deriving(Show) for most basic data types, wouldn't it be possible to have something similar but then deriving(Pretty). When printing ASTs it could make it much easier to look at the output. With regards, Christophe -- Christophe Poucet Ph.D. Student Phone:+32 16 28 87 20 E-mail: Christophe (dot) Poucet (at) imec (dot) be Website: http://notvincenz.com/ IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be *DISCLAIMER* This e-mail and/or its attachments may contain confidential information. It is intended solely for the intended addressee(s). Any use of the information contained herein by other persons is prohibited. IMEC vzw does not accept any liability for the contents of this e-mail and/or its attachments. ** ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC wish
Hello Chris,
It seems that your reply only replied to me and not to the haskell-cafe
list. I hope you do not mind that I reply to the list. Anyways,
regarding how the AST is pretty printed. I was not thinking of any
highlevel pretty printing of an AST (at least not derived
automatically). The type of pretty printing I was thinking of would be
synonymous to what deriving Show would give you for any type, except
that it would be layed out a bit more cleanly with indentation and newlines.
Here is an example:
data Foo = Foo {unFoo :: [Bar]}
data Bar = Bar {unBar :: Int}
prettyPrint . Foo. map Bar $ [1..10]
Foo {
unFoo = [
Bar {unBar = 1},
Bar {unBar = 2},
..
Bar {unBar =10}
]
}
Jared: Thank you for mentioning DrIFT. Will certainly take a look at it :)
Cheers,
Christophe
Christopher Brown wrote:
Christophe,
But that depends on what you think is the correct way of displaying
an AST. I can personally think of a few ways an AST could be pretty
printed.
Chris.
On 24 May 2006, at 00:05, Christophe Poucet wrote:
Dear all,
I recently stumbled upon something that I think should be added to
the GHC wishlist. Not knowing where to put it, I will put it here.
As there is deriving(Show) for most basic data types, wouldn't it be
possible to have something similar but then deriving(Pretty). When
printing ASTs it could make it much easier to look at the output.
With regards,
Christophe
--
Christophe Poucet
Ph.D. Student
Phone:+32 16 28 87 20
E-mail: Christophe (dot) Poucet (at) imec (dot) be
Website: http://notvincenz.com/ IMEC vzw – Register of Legal
Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven,
Belgium – www.imec.be
*DISCLAIMER*
This e-mail and/or its attachments may contain confidential
information. It is intended solely for the intended addressee(s).
Any use of the information contained herein by other persons is
prohibited. IMEC vzw does not accept any liability for the contents
of this e-mail and/or its attachments.
**
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Christophe Poucet
Ph.D. Student
Phone:+32 16 28 87 20
E-mail: Christophe (dot) Poucet (at) imec (dot) be
Website: http://notvincenz.com/
IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be
*DISCLAIMER*
This e-mail and/or its attachments may contain confidential information. It is
intended solely for the intended addressee(s).
Any use of the information contained herein by other persons is prohibited.
IMEC vzw does not accept any liability for the contents of this e-mail and/or
its attachments.
**
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Dynamically stackable monads
Hello,I was wondering if it's possible to stack a runtime-known amount ofmonads on top of each other. Let me illustrate. Assume I have a monadthat can consume data and expects as starting parameter an action of the
underlying monad to use this data (call it produce at the lower levelmonad).Now one could imagine stacking one of these consumers on top of theother, as can be seen below. However I can not choose at runtime how
many I want to stack. Is there any solution for this?Regards,Christophe{-# OPTIONS_GHC -fglasgow-exts #-}
module Main whereimport Control.Monadimport Control.Monad.Identityimport Control.Monad.Stateimport Control.Monad.Transdata Action e m = Action { produce :: e - m ()}newtype SequencerT e m a = SequencerT (StateT (Action e m) m a)
deriving (Functor, Monad, MonadIO)newtype Sequencer e a = Sequencer (SequencerT e Identity a) deriving (Functor, Monad, MonadSequencer e)instance MonadTrans (SequencerT e) where lift = SequencerT . lift
class Monad m = MonadSequencer e m | m - e where consume :: e - m ()instance Monad m = MonadSequencer e (SequencerT e m) where consume x = SequencerT $ do s - get
lift . (produce s) $ xevalSequencerT (SequencerT s) action =""> evalStateT s actionevalSequencer (Sequencer s) inputs action =""> evalSequencerT s actionrunSequencerT (SequencerT s) action =
""> runStateT s actionrunSequencer (Sequencer s) action =""> runSequencerT s actionmain :: IO () = evalSequencerT (evalSequencerT (consume 1 consume 2 consume 3) (Action{produce = \x - if x 1 then consume x else liftIO . print $ (A ++ show x)}))
(Action{produce = print . (B ++) . show })--Christophe PoucetPh.D. StudentPhone:+32 16 28 87 20E-mail: ---
IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be
*DISCLAIMER*This e-mail and/or its attachments may contain confidential information. It is intended solely for the intended addressee(s).Any
use of the information contained herein by other persons is prohibited.
IMEC vzw does not accept any liability for the contents of this e-mail
and/or its attachments.**
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Advice needed on best way to simulate an STL vector
Either way,
Even an STL vector has O(N) insert because it needss to shift all the
items past the current element where insertion is taking place. If your
application is insert intensive the most ideal structure is a map.
Concerning the suggestion regarding doubling the capacity, I don't
believe that STL actually doubles the allocated size. Most applications
that use vector-like data structures (STL Vector, Ruby Array) typically
use the fibonacci sequence for the sizes because the doubling grows too
fast.
Cheers
Cale Gibbard wrote:
Oops, replace Array there with DiffArray.
On 19/04/06, Cale Gibbard [EMAIL PROTECTED] wrote:
Well, you could use something like C++ does for implementing STL
vectors in terms of arrays -- iirc, it generally doubles the allocated
size each time applying an operation to the vector would make it
exceed its capacity (the current allocation size), and keeps track of
the actual number of elements stored separately. It's important to do
allocation which is proportional to the existing capacity, or repeated
insertion will become quadratic time rather than linear. So
essentially, some data structure like
data Vector a = Vector { store :: Array Int a, end :: Int }
would be a sufficient minimal way to start. When the store needs to be
increased, you simply create a new array with twice as many elements,
copy the initial elements in from the old array which is then thrown
away, and only update end to the position of the actual last element.
This is analogous to what C++ implementations of the vector class do.
What will bite you is if you try to generalise from indices of type
Int to instances of Ix -- the Ix operations assume that there are
lower and upper bounds on indices. The upper bound of course quickly
becomes a problem. You could however use Enum, which has toEnum and
fromEnum, which are sufficient to use with the implementation in terms
of Ints. It could also be claimed that Int isn't always the best
initial type to use, and indeed I'd still feel safer with Integer
somehow, but then, fromEnum and toEnum use Int, and if you have more
than 2 billion elements in your vector at the same time, maybe you
should be looking at your algorithm more carefully and/or doing your
own low level memory allocation via FFI. :)
- Cale
On 19/04/06, Brian Hulley [EMAIL PROTECTED] wrote:
Hi -
In C++, STL provides a vector class which behaves as an array except you can
insert/delete elements from it. I'm wondering what is the best Haskell data
structure to use to simulate this, either mutable or immutable.
I've looked at the Array interface, but although there is the // operation
to replace some elements, there does not appear to be a simple way to
delete/insert elements.
Ideally I'd like functions like:
-- Insert new elements starting at the specified index, moving the others up
to make room
insert:: Array i e - i - [e] - Array i e
-- Delete a range of elements, moving later elements back down
delete:: Array i e - i - i - Array e
-- Append a new element to the end of an array
push_back :: Array i e - e - Array i e
Is there an efficient way of implementing these operations in Haskell, based
on arrays, or should I be using some other data structure altogether eg a
list?
Also, for large arrays, am I right in thinking that it is still more
efficient to use immutable arrays rather than mutable arrays (because it is
easier for gc to always just deal with immutable values)?
Thanks, Brian.
___
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] C++ parser in Haskell?
I would be very interested in this as well. I have looked myself but haven't found anything else. I wrote one myself in Haskell but for a subset of C++ (subset of C but with some extra things like methods). Christophe Poucet Ravi Nanavati wrote: It turns out we might find such a beast useful at Bluespec. If anyone has written a C++ parser in Haskell (or knows of one), we'd like to hear about it. Thanks, - Ravi Nanavati Bluespec, Inc. ___ 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] C++ parser in Haskell?
For the parsing and lexing I used happy and alex. Jake Luck wrote: I would be very interested in this as well. I have looked myself but haven't found anything else. I wrote one myself in Haskell but for a subset of C++ (subset of C but with some extra things like methods). Did you build it using parsec or happy? jake ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Christophe Poucet Ph.D. Student Phone:+32 16 28 87 20 E-mail: [EMAIL PROTECTED] IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be *DISCLAIMER* This e-mail and/or its attachments may contain confidential information. It is intended solely for the intended addressee(s). Any use of the information contained herein by other persons is prohibited. IMEC vzw does not accept any liability for the contents of this e-mail and/or its attachments. ** ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GUI-Woes
I have to concur with Duncan.I started using Gtk2Hs for a small project and literally within a couple hours I had a good understanding upon which to build a nice gui as well as the gui itself. I haven't tried out wxhaskell, but trying gtk2hs and it's cairo bindings, I fell in love with the simplicity. CheersOn 3/13/06, Duncan Coutts [EMAIL PROTECTED] wrote: On Mon, 2006-03-13 at 09:58 +0100, Daniel Fischer wrote: Hello All, how would I get myself a working (and easy to use) GUI-library?There are two main GUI libraries at the moment: Gtk2Hs and wxHaskell. http://haskell.org/gtk2hs/http://wxhaskell.sourceforge.net/Both will work with current versions of GHC etc. You can either use distro packages if they're available for your distro or build fromsource.Personally I'd recommend Gtk2Hs but then I'm biased because I helpmaintain Gtk2Hs :-).Duncan___ Haskell-Cafe mailing listHaskell-Cafe@haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
