Re: [Haskell-cafe] vector-simd: some code available, and some questions
I've not been following this thread very closely, but it seems like what you're trying to do may be related to Geoffrey Mainland's work on SIMD support in GHC. See [1] for his SIMD-enabled version of the vector library. He's also written some blog posts about this [2]. Reiner [1] https://github.com/mainland/vector [2] http://ghc-simd.blogspot.com.au/ On 8 July 2012 05:13, Nicolas Trangez nico...@incubaid.com wrote: All, After my message of yesterday [1] I got down to it and implemented something along those lines. I created a playground repository containing the code at [2]. Initial benchmark results at [3]. More about the benchmark at the end of this email. First some questions and requests for help: - I'm stuck with a typing issue related to 'sizeOf' calculation at [4]. I tried a couple of things, but wasn't able to figure out how to fix it. - I'm using unsafePerformIO at [5], yet I'm not certain it's OK to do so. Are there better (safer/performant/...) ways to get this working? - Currently Alignment phantom types (e.g. A8 and A16) are not related to each other: a function (like Data.Vector.SIMD.Algorithms.unsafeXorSSE42) can have this signature: unsafeXorSSE42 :: Storable a = SV.Vector SV.A16 a - SV.Vector SV.A16 a - SV.Vector SV.A16 a Yet, imaging I'd have an SV.Vector SV.A32 Word8 vector at hand, the function should accept it as well (a 32-byte aligned vector is also 16-byte aligned). Is there any way to encode this at the type level? That's about it :-) As of now, I only implemented a couple of the vector API functions (the ones required to execute my benchmark). Adding the others should be trivial. The benchmark works with Data.Vector.{Unboxed|Storable}.Vector (UV and SV) vectors of Word8 values, as well as my custom Data.Vector.SIMD.Vector type (MV) using 16-byte alignment (MV.Vector MV.A16 Word8). benchUV, benchSV and benchMV all take 2 pre-calculated Word8 vectors of given size (1024 and 4096) and xor them pairwise into the result using zipWith xor. benchMVA takes 2 suitable MV vectors and xor's them into a third using a rather simple and unoptimized C implementation using SSE4.2 intrinsics [6]. This could be enhanced quite a bit (I guess using the prim calling convention, FFI overhead can be reduced as well). Currently, only vectors of a multiple of 32 bytes are supported (mostly because of laziness on my part). As you can see, the zipWith Data.Vector.SIMD implementation is slightly slower than the Data.Vector.Storable based one. I didn't perform much profiling yet, but I suspect allocation and ForeignPtr creation is to blame, this seems to be highly optimized in GHC.ForeignPtr.mallocPlainForeignPtrBytes as used by Data.Vector.Storable. Thanks for any input, Nicolas [1] http://www.haskell.org/pipermail/haskell-cafe/2012-July/102167.html [2] https://github.com/NicolasT/vector-simd/ [3] http://linode2.nicolast.be/files/vector-simd-xor1.html [4] https://github.com/NicolasT/vector-simd/blob/master/src/Data/Vector/SIMD/Algorithms.hs#L46 [5] https://github.com/NicolasT/vector-simd/blob/master/src/Data/Vector/SIMD/Algorithms.hs#L43 [6] https://github.com/NicolasT/vector-simd/blob/master/cbits/vector-simd.c#L47 ___ 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] Helper classes for Generics
Hi all, I've been playing with GHC's new generics features (see http://www.haskell.org/ghc/docs/latest/html/users_guide/generic-programming.html). All the documentation I've seen suggests creating a helper class -- for instance, the GSerialize class in the above link -- on which one defines generic instances. It seems to me that this isn't necessary. For example, here's the the example from the GHC docs, but without a helper class: -- set the phantom type of Rep to (), to avoid ambiguity from0 :: Generic a = a - Rep a () from0 = from data Bit = O | I class Serialize a where put :: a - [Bit] default put :: (Generic a, Serialize (Rep a ())) = a - [Bit] put = put . from0 instance Serialize (U1 x) where put U1 = [] instance (Serialize (a x), Serialize (b x)) = Serialize ((a :*: b) x) where put (x :*: y) = put x ++ put y instance (Serialize (a x), Serialize (b x)) = Serialize ((a :+: b) x) where put (L1 x) = O : put x put (R1 x) = I : put x instance (Serialize (a x)) = Serialize (M1 i c a x) where put (M1 x) = put x instance (Serialize a) = Serialize (K1 i a x) where put (K1 x) = put x Is there a reason to prefer using helper classes? Or perhaps we should update the wiki page (http://www.haskell.org/haskellwiki/Generics) to avoid using helper classes? Regards, Reiner___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Analyzing slow performance of a Haskell program
On 9 August 2011 10:06, Bryan O'Sullivan b...@serpentine.com wrote: On Mon, Aug 8, 2011 at 9:24 AM, Chris Yuen kizzx2+hask...@gmail.comwrote: For reference I have asked the same question on StackOverflow. One person suggested that the reason might be that Int64 on Windows is broken ( http://stackoverflow.com/questions/6970904/analyzing-slow-performance-of-a-haskell-program/6976448#6976448 ). No, they're barking up the wrong tree. I've put an idiomatic Haskell translation of your C++ algorithm at https://gist.github.com/1133048#file_wordy.hs (I've also included a copy of your original C++, with a bug fixed, in the same gist.) As you can see, the two are almost identical. Not surprisingly, each one spends the bulk of its time computing word lengths. GHC simply doesn't do a great job of compiling fairly tight code like this. gcc generates about 100 lines of assembly that's mostly easy to follow (except for some bit-twiddling tricks to avoid div instructions). Although the Core it generates looks fine, GHC spends quite a bit of time in its generated assembly on what looks to me like STG housekeeping (it spends only 0.3% of its time in the garbage collector, because it doesn't allocate memory). The overall result is that the Haskell code runs about 5x more slowly than the C++ code. GHC generating bad assembly suggests trying the llvm codegen (see http://donsbot.wordpress.com/2010/02/21/smoking-fast-haskell-code-using-ghcs-new-llvm-codegen/). Compiling Bryan's code with $ ghc -O2 -fllvm Wordy.hs it now runs only 2x slower than the C++ code. Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] yi + cabal-dev
I've not tried this myself, but you could look at the -fhacking flag. It's documented in the README.md file, which claims it compiles yi without dynamic reconfiguration, and instead uses HackerMain.hs as your (static) configuration file. Reiner On 22/06/11 11:55, Alex Rozenshteyn wrote: I'm trying to run yi. More precisely, I'm trying to run yi in its own sandbox, created by cabal-dev. yi uses dyre to recompile its config file. Unsurprisingly, this fails, since ghc doesn't know anything about the yi install unless pointed to a separate package database. Has anyone gotten a similar setup to work, or does anyone have any suggestions? -- Alex R ___ 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] Compiler constraints in cabal
Ah, I hadn't thought of that. But doesn't the version of GHC change much more often than the version of base does? Reiner On 6 November 2010 03:49, Ozgur Akgun ozgurak...@gmail.com wrote: AFAIK, the way to do this is putting constraints on the base package. On 5 November 2010 14:59, Reiner Pope reiner.p...@gmail.com wrote: Hi, I have a library, hmatrix-static, on Hackage. Version 0.3 (the current version) compiles with ghc-6.12. Let's say I want to upgrade my library using new features in ghc-7.0, and then release these upgrades as version 0.4. Is there any way to state in my cabal file that this new version will no longer compile under ghc-6.12? The reason I would like to state this is so that a user with ghc-6.12 can do 'cabal install hmatrix-static' (or do a cabal install of a program depending on hmatrix-static) and see that cabal will install version 0.3 rather than attempt to install version 0.4 and fail. Thanks for your help. Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ozgur Akgun ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compiler constraints in cabal
I was aware of this condition, but I'm not precisely sure it addresses my requirements. When you run cabal install some-package, cabal reads all version constraints listed in the build-depends field, and chooses which versions of which packages to download from Hackage in order to satisfy these constraints. I want to expose my dependency on a particular version of ghc to cabal's constraint satisfier. The end result I want is that when you type cabal install hmatrix-static with ghc-6.12 installed, then cabal chooses hmatrix-static-0.3; and when you type cabal install hmatrix-static with ghc-7.0 installed, then cabal chooses hmatrix-static-0.4. As I understand it, using impl(ghc = 7.0) won't achieve this. The closest thing I can think of is to write my hmatrix-static.cabal file for version 0.4 as: ... if impl(ghc 7.0) build-depends: nonexistant-package ... so that cabal cannot satisfy the constraints for hmatrix-static-0.4 unless I have ghc = 7.0. This seems a little hacky, and I'm also not sure if it works. (I'm finding it rather hard to test these ideas, because I don't want to upload a new package to Hackage every time...) All the best, Reiner On 6 November 2010 19:24, wren ng thornton w...@freegeek.org wrote: On 11/6/10 3:13 AM, Ivan Lazar Miljenovic wrote: On 6 November 2010 17:52, Reiner Popereiner.p...@gmail.com wrote: Ah, I hadn't thought of that. But doesn't the version of GHC change much more often than the version of base does? Each major version of GHC has a different (major) version of base. I think you can also say stuff like ghc= 6.10, but I'm not sure. The correct condition notation is: impl(ghc = 6.10) -- 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
[Haskell-cafe] Compiler constraints in cabal
Hi, I have a library, hmatrix-static, on Hackage. Version 0.3 (the current version) compiles with ghc-6.12. Let's say I want to upgrade my library using new features in ghc-7.0, and then release these upgrades as version 0.4. Is there any way to state in my cabal file that this new version will no longer compile under ghc-6.12? The reason I would like to state this is so that a user with ghc-6.12 can do 'cabal install hmatrix-static' (or do a cabal install of a program depending on hmatrix-static) and see that cabal will install version 0.3 rather than attempt to install version 0.4 and fail. Thanks for your help. Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] proposal: point free case expressions
2009/11/5 Sebastiaan Visser sfvis...@cs.uu.nl: Hello all, Wouldn't it be nice if we could write point free case statements? I regularly find myself writing down something like this: myFunc = anotherFunc $ \x - case x of Left err - print err Right msg - putStrLn msg We could really use a case statement in which we skip the scrutinee and make `(case of {})' be syntactic sugar for `(\x - case x of {})'. So we could write: myFunc = anotherFunc $ case of Left err - print err Right msg - putStrLn msg A minor syntactical addition, a big win! Cheers, -- Sebastiaan Visser ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Morten Rhiger implemented Type-safe pattern combinators [1], which are essentially a library for pattern matching, entirely within Haskell98. As an example, he implemented anonymous pattern-matching with this library, which is similar to what you ask for. It would be certainly be possible to implement your proposal with his library. My library first-class-patterns [2] on Hackage essentially follows Morten Rhiger's approach, but makes the types more understandable. I implemented point free case expressions (the 'elim' function) and monadic pattern matches (the 'mmatch' function) in version 0.2.0, which I just uploaded. For instance, you could write import Data.Pattern anonymous matching ex6 :: Show a = Either a String - IO () ex6 = elim $ left var - print | right var - putStrLn -- monadic matching ex8 :: IO () ex8 = mmatch getLine $ cst - return () | var- putStrLn . (You said ++) Cheers, Reiner [1] http://www.itu.dk/people/mir/typesafepatterns.pdf [2] http://hackage.haskell.org/package/first-class-patterns ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] SpecConstr difficulties
Hi everyone, I've been having some trouble getting SpecConstr to work as I want it to. The following example (see end of email) came up in some code I was playing around with. The loops g1 and g2 both compute the same thing: the maximum element of the list (which has been fused away) of numbers from 1 to 10. Since 'maximum' is a foldl1 not a foldl, I use a strict Maybe type as an accumulator. The Maybe gets filled after the first element is seen, so the Maybe is a Just for almost the entire running of the loop. It would be good to have this recognised by SpecConstr, to create an optimised loop for the Just case. This does indeed happen for g1, but not for g2. My difficulty is that I am only able to produce code similar to g2, i.e. where the pattern matching is in a separate function, 'expose', because the 'expose' function is implemented in a type-class, like in stream-fusion. Is there some way to keep the SpecConstr while leaving the 'expose' as a separate function? Here is the code: {-# LANGUAGE BangPatterns #-} module Test(ans1,ans2) where import Prelude hiding(Maybe(..)) data Maybe a = Just !a | Nothing Nothing `mapp` Just b = Just b Just a `mapp` Just b = Just (max a b) ans1 = g1 Nothing (0::Int) g1 m !n = case m of Nothing - if n 10 then m else g1 (m `mapp` Just n) (n+1) Just x - if n 10 then m else g1 (m `mapp` Just n) (n+1) ans2 = g2 Nothing (0::Int) g2 m !n = expose m (if n 10 then m else g2 (m `mapp` Just n) (n+1)) expose Nothing b = b expose (Just a) b = a `seq` b On a similar note, when I was having difficulties with this problem, I started to wonder if it would be possible to come up with a more direct way to tell GHC, do SpecConstr on this variable. From reading the source code of the stream-fusion package, it seems that the current way of doing this is with 'expose' functions like I wrote below. Could we instead have a {-# SPECCONSTR #-} pragma, to be used on function arguments, like: foo {-# SPECCONSTR #-} x y {-# SPECCONSTR #-} z = ... This pragma should say to the GHC something like ignore conditions H2, H5 and H6 of the SpecConstr paper, for this function and this argument. Cheers, Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stream-fusion without the lists
2009/5/13 Don Stewart d...@galois.com: rl: On 12/05/2009, at 14:45, Reiner Pope wrote: The Stream datatype seems to be much better suited to representing loops than the list datatype is. So, instead of programming with the lists, why don't we just use the Stream datatype directly? I think the main reason is that streams don't store data and therefore don't support sharing. That is, in let xs = map f ys in (sum xs, product xs) the elements of xs will be computed once if it is a list but twice if it is a stream. The other issue is reminding developers to preserve stream invariants, so as not to break the heavy duty rewriting that's going to happen to their code. Can you elaborate on this please? I've only seen a few invariants mentioned when reading the Stream Fusion paper and the stream-fusion source code. They are: 1. 'Skip' values should have no semantic significance. 2. Don't construct bottom Streams. However, this seems to only apply when the fusion rewrite rule is applied, which is not the case I am talking about. Cheers, Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Stream-fusion without the lists
Hi everyone, With stream-fusion, we can write functions which construct and destruct lists, such as (this is the main example from the Stream Fusion paper[1]) f :: Int - Int f n = sum [k * m | k - [1..n], m - [1..k]] and the rewrite rules in stream-fusion replace these operations on lists with fusible operations on the Stream (non-recursive) datatype. In this example, the domain and codomain of the function don't mention the list datatype. There seem to be many functions like this: the lists are being used internally as composable loops rather than as data-structures. The Stream datatype seems to be much better suited to representing loops than the list datatype is. So, instead of programming with the lists, why don't we just use the Stream datatype directly? For example: In Data.Stream (from the stream-fusion package) we can find most of the Prelude list functions but with Stream in all the types instead of []. For example, Data.Stream.sum :: Num a = S.Stream a - a Using this module, we can rewrite f without mentioning lists. We first need a Monad instance for Data.Stream.Stream: import qualified Data.List.Stream as S instance Monad S.Stream where return = S.return (=) = S.concatMap Now we can write f :: Int - Int f n = S.sum $ do k - S.enumFromToInt 1 n m - S.enumFromToInt 1 k return (k*m) which is essentially the same as the original f, although lacking the syntactic sugar of the list comprehension. To me, it seems that Stream is more sensible data type to use than [] when the algorithm being expressed is just a loop (rather than something which needs a [] as a cache/buffer), for the following reasons: 1. If I am programming with lists and I need some function which I can't express with Prelude functions, I have to write it myself. I will probably lose fusion in this case, because I will write it recursively in terms of lists. On the other hand, if I am programming with Streams, I will write it myself in terms of Streams, and it should be easier to maintain fusion because it won't be recursive. 2. Holding on to a [] too long can cause a space leak. This is not the case for Stream, because a Stream only ever contains one state. More generally, the memory use of Stream is more easily predictable than that of [], since running a Stream only holds on to one state at a time, and we often know how big the state is. 3. Fusion doesn't rely on rewrite rules firing. I consider this point less significant than the other two. So, thoughts? Do people program with Streams directly? What have I not considered? Cheers, Reiner [1] http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What are side effects in Haskell?
2009/1/3 Conal Elliott co...@conal.net: Are there other thoughts insights about the source of the idea that everything is a function? Lazy evaluation can make values seem like functions, given that laziness can be modeled in a strict imperative language by 0-argument functions. Also, in an uncurried language, decreasing the number of arguments to a function, still keeps it a function, eg foo(int a, int b); // 2 arguments foo(int a); // 1 argument foo(); // 0 arguments, but still a function In a strict language, there is a distinction between 0-argument functions and values; there isn't in Haskell, but it is still nice to maintain the idea of 0-argument functions in Haskell -- which are just values. Cheers, Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is this related to monomorphism restriction?
On Sun, Dec 21, 2008 at 10:28 AM, Maurício briqueabra...@yahoo.com wrote: Hi, Why isn't the last line of this code allowed? f :: (TestClass a) = a - Integer f = const 1 a = (f,f) g = fst a The only thing I can think about is monomorphism restriction, but it's allowed (or even the third line would not be accepted). Is there something I could read to understand that? Thanks, Maurício ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe The monomorphism restriction refuses to accept the definition of a. However, even if we turn the monomorphism restriction off there is still a problem. {-# LANGUAGE NoMonomorphismRestriction #-} f :: (TestClass a) = a - Integer f = const 1 a = (f,f) g = fst a In this case, the definition of a is accepted, but not the definition of g. The reason is that a has type a :: (TestClass a, TestClass b) = (a,b) and then when we take 'fst' of this value (as in g) we get g :: (TestClass a, TestClass b) = a which is an ambiguous type, since there is no way to tell the compiler what 'b' is when running g. Cheers, Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec and type level numerals
On Sun, Dec 14, 2008 at 6:54 AM, David Menendez d...@zednenem.com wrote: 2008/12/13 Nathan Bloomfield nblo...@gmail.com: I want to be able to parse a string of digits to a type level numeral as described in the Number parameterized types paper. After fiddling with the problem for a while, I'm not convinced it's possible- it seems as though one would need to know the type of the result before parsing, but then we wouldn't need to parse in the first place. :) This can be done with existential types. I think Oleg Kiselyov has an example somewhere of a parser that determines the type of its output from its input, but here's the basic idea: data SomeCard = forall a. (Card a) = SomeCard a Now you can define parseP :: Parser SomeCard Unfortunately, all you know about the value inside the SomeCard is that it's a member of the class Card, which may not be very helpful. Depending on how general you want to be, you can bundle more operations with SomeCard, or you can return a GADT that reflects the type-level natural at the value level. -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Depending on what you actually want to do, you may be looking for Oleg Kiselyov's reifyIntegral function, which he defines in the paper Functional Pearl: Implicit Configurations -- or Type Classes Reflect the Value of Types (at http://www.cs.rutgers.edu/~ccshan/prepose/prepose.pdf ). It has type something like reifyIntegral :: forall a. Int - (forall n. Numeral n = n - a) - a encoding n's existential type with continuation passing style. Cheers, Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fixity parsing, Template Haskell
It turns out that there is at least a (partial) solution to my quasiquote problem. Template Haskell's reify function can be used to find an operator's fixity, although it seems not for all cases. However, for the purposes of this discussion, suppose I can write a function userFixity :: String - Q Fixity which takes a operator used in user code and returns its fixity, in the Q monad (Template Haskell's monad). I want this information to be used somehow when creating the Template Haskell AST, so that the operators used have the correct fixities. If I use HSE for parsing Haskell expressions, then I want it to tell me where it unsure of the fixities, so that I can insert the correct ones there. For this use case, I would want HSE to use an AST like I suggested, because it allows the parser to say, I'm not sure what the correct fixity is. Cheers, Reiner On Sun, Nov 23, 2008 at 8:23 AM, John A. De Goes [EMAIL PROTECTED] wrote: Though many see it as losing information, I agree wholeheartedly with your proposal to change the AST. It's better to have an AST that conveys less information, but truthfully, than to have an AST that purports to convey more information, when in fact that information is false. In most languages, some things just can't be known at parse time. They need to be resolved later. In this case, the most important thing is following the principle of least surprise: A Haskell expression inside a quasiquote should work the same as a Haskell expression outside a quasiquote. Violating the principle of least surprise is one of the most grievous mistakes language (and interface) designers make. Regards, John A. De Goes N-BRAIN, Inc. http://www.n-brain.net [n minds are better than n-1] On Nov 22, 2008, at 9:02 AM, Reiner Pope wrote: It seems to me that fixity information behaves more like semantics than like syntax. For instance, fixities may be imported, and obey namespacing rules. Knowing and correctly handling these rules seems beyond the scope of a mere parser: I would hope that a single Haskell file could be parsed without reference to any files, and fixity declarations seem to be just about the only thing which prevent this -- hence my suggestion to change the AST in order to regain this property. The use I envision of it is as I described: writing a quasiquoter using HSE to parse the user's Haskell expressions. The problem is that, for such a case, HSE (or any other parser) is forced to parse infix expressions for which it cannot possibly know the correct fixities. Any result with more information than the list form I gave would be a lie. I realise that I don't know how fixities are implemented in Haskell compilers, so perhaps I'm misunderstanding how they are treated. Cheers, Reiner On Sat, Nov 22, 2008 at 11:54 PM, Niklas Broberg [EMAIL PROTECTED] wrote: Of course, this would require a change to Template Haskell, so a second-best solution would be to forbid unparenthesised expressions in my quasiquoter. Then, parsing can proceed correctly without knowing the fixities. This would be easiest to do if haskell-src-exts changed its AST in a similar way to described above for Template Haskell. I'm not sure I follow you here. In what way would it be simpler if HSE changes its AST to a less-information constructor? I won't do that, for the same reason you point out with TH and disadvantages when using it as a library, though I'm still curious what uses you envision and how it would be made easier. I'm still in the process of designing the fixity support for HSE, and all input is valuable. :-) Cheers, /Niklas ___ 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] Fixity parsing, Template Haskell
On Mon, Nov 24, 2008 at 12:39 AM, Niklas Broberg [EMAIL PROTECTED] wrote: I want this information to be used somehow when creating the Template Haskell AST, so that the operators used have the correct fixities. If I use HSE for parsing Haskell expressions, then I want it to tell me where it unsure of the fixities, so that I can insert the correct ones there. For this use case, I would want HSE to use an AST like I suggested, because it allows the parser to say, I'm not sure what the correct fixity is. As noted above, I really don't like that change. If you use HSE for parsing expressions, it would *never* know the correct fixities, and you would always get a completely left-biased tree. Why would that be harder to work with? I understand the argument about least surprise, and that this feature must be strongly documented (which it currently isn't), but for practical purposes I don't see why the current state would be problematic. It should even be trivial to convert the left-biased tree into an intermediate structure exactly like the one you suggest, no? No, I believe it wouldn't. The left-biased tree cannot distinguish where parentheses have been used from where HSE inserted its own left fixities. For instance, if we have the expressions xs ++ ys ++ zs (xs ++ ys) ++ zs Then HSE will return something like (I'm using strings for the subexpression parses, for simplicity) InfixE (InfixE xs ++ ys) ++ zs for both the first and second parses. However, if I then use the knowledge that ++ is right infix, I will want to convert the first, but not the second parses into right infix. I can't do this, because they are both parsed the same way. I would also like to point out that a list representation as I suggested can in fact encode the correct fixities if they are known to HSE. This is true simply because the list constructor is isomorphic to the current constructor in the special case where the list of operators has length 1. For instance, in the first example above, if HSE somehow knew that ++ is right infix, it should return a parse result of InfixE [xs, InfixE [ys, zs] [++]] [++] rather than just InfixE [xs, ys, zs] [++, ++] Cheers, Reiner Cheers, /Niklas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fixity parsing, Template Haskell
It seems to me that fixity information behaves more like semantics than like syntax. For instance, fixities may be imported, and obey namespacing rules. Knowing and correctly handling these rules seems beyond the scope of a mere parser: I would hope that a single Haskell file could be parsed without reference to any files, and fixity declarations seem to be just about the only thing which prevent this -- hence my suggestion to change the AST in order to regain this property. The use I envision of it is as I described: writing a quasiquoter using HSE to parse the user's Haskell expressions. The problem is that, for such a case, HSE (or any other parser) is forced to parse infix expressions for which it cannot possibly know the correct fixities. Any result with more information than the list form I gave would be a lie. I realise that I don't know how fixities are implemented in Haskell compilers, so perhaps I'm misunderstanding how they are treated. Cheers, Reiner On Sat, Nov 22, 2008 at 11:54 PM, Niklas Broberg [EMAIL PROTECTED] wrote: Of course, this would require a change to Template Haskell, so a second-best solution would be to forbid unparenthesised expressions in my quasiquoter. Then, parsing can proceed correctly without knowing the fixities. This would be easiest to do if haskell-src-exts changed its AST in a similar way to described above for Template Haskell. I'm not sure I follow you here. In what way would it be simpler if HSE changes its AST to a less-information constructor? I won't do that, for the same reason you point out with TH and disadvantages when using it as a library, though I'm still curious what uses you envision and how it would be made easier. I'm still in the process of designing the fixity support for HSE, and all input is valuable. :-) Cheers, /Niklas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fixity parsing, Template Haskell
This post follows on from a discussion about a month ago, called Haskell Syntax Inside Quasiquote. To summarise, suppose I want to create a Haskell quasiquoter for lists, eg [$list|1,x^2,y,3|] (representing the list [1,x^2,y,3]) Ideally, this would allow arbitrary Haskell expressions for each element of the list (provided, of course, that the types are correct). To write this list quasiquoter, I would need to parse Haskell expressions. This is doable[1], but is necessarily buggy when infix operators are concerned. For instance, a user of the list quasiquoter may define two new operators, (+*) and (+^), and then write [$list|1+*2+^3|] Being able to correctly parse such an expression depends on known the two operator's fixities, which is currently impossible. The problem is that potentially non-local fixity declarations affect parsing. As far as I can see, the correct solution is to change the Template Haskell AST representation of fixity expressions from data Exp = ... | InfixE (Maybe Exp) Exp (Maybe Exp) to something like type Op = Exp --- because TH doesn't distinguish operators from expressions data Exp = ... | InfixE [Exp] [Op] --- length [Exp] == 1 + length [Op], always | LeftSection Exp Op | RightSection Op Exp Apart from splitting of the sections, the important difference is that the expressions are parsed as a list of expressions separated by operators. So, my example above would be parsed as something like InfixE [parseExp 1, parseExp 2, parseExp 3] [+*, +^] Then, when Template Haskell performs the splice, it could correctly resolve the fixities. Of course, this would require a change to Template Haskell, so a second-best solution would be to forbid unparenthesised expressions in my quasiquoter. Then, parsing can proceed correctly without knowing the fixities. This would be easiest to do if haskell-src-exts changed its AST in a similar way to described above for Template Haskell. Any thoughts? Cheers, Reiner Pope [1] For instance, see haskell-src-meta, which uses haskell-src-exts as a parser, and then converts the AST into a form that Template Haskell recognises. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Fixity parsing, Template Haskell
It occurs to me that changing the Template Haskell representation to a less-information representation is disadvantageous when code has been reified for examination by a Template Haskell-using library. In that case, the library would want maximum knowledge about the fixities. Perhaps the best solution is just to forbid unparenthesised infix expressions in the quasiquote language. Cheers, Reiner On Fri, Nov 21, 2008 at 11:59 PM, Reiner Pope [EMAIL PROTECTED] wrote: This post follows on from a discussion about a month ago, called Haskell Syntax Inside Quasiquote. To summarise, suppose I want to create a Haskell quasiquoter for lists, eg [$list|1,x^2,y,3|] (representing the list [1,x^2,y,3]) Ideally, this would allow arbitrary Haskell expressions for each element of the list (provided, of course, that the types are correct). To write this list quasiquoter, I would need to parse Haskell expressions. This is doable[1], but is necessarily buggy when infix operators are concerned. For instance, a user of the list quasiquoter may define two new operators, (+*) and (+^), and then write [$list|1+*2+^3|] Being able to correctly parse such an expression depends on known the two operator's fixities, which is currently impossible. The problem is that potentially non-local fixity declarations affect parsing. As far as I can see, the correct solution is to change the Template Haskell AST representation of fixity expressions from data Exp = ... | InfixE (Maybe Exp) Exp (Maybe Exp) to something like type Op = Exp --- because TH doesn't distinguish operators from expressions data Exp = ... | InfixE [Exp] [Op] --- length [Exp] == 1 + length [Op], always | LeftSection Exp Op | RightSection Op Exp Apart from splitting of the sections, the important difference is that the expressions are parsed as a list of expressions separated by operators. So, my example above would be parsed as something like InfixE [parseExp 1, parseExp 2, parseExp 3] [+*, +^] Then, when Template Haskell performs the splice, it could correctly resolve the fixities. Of course, this would require a change to Template Haskell, so a second-best solution would be to forbid unparenthesised expressions in my quasiquoter. Then, parsing can proceed correctly without knowing the fixities. This would be easiest to do if haskell-src-exts changed its AST in a similar way to described above for Template Haskell. Any thoughts? Cheers, Reiner Pope [1] For instance, see haskell-src-meta, which uses haskell-src-exts as a parser, and then converts the AST into a form that Template Haskell recognises. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Type question in instance of a class
ATs are Associated Types, aka Type Families. They can be found in the GHC 6.10 manual here: http://haskell.org/ghc/docs/6.10.1/html/users_guide/type-families.html As a starting point, you might want to try something like: class Complex c where type RealType c realPart :: c - RealType c imagPart :: c - RealType c Cheers, Reiner On Tue, Nov 18, 2008 at 7:01 PM, Maurício [EMAIL PROTECTED] wrote: (...) One way to code this would be to use functional dependencies: class MyClass r s | r - s where function :: r - s One additional problem is that I (believe I) need that my class takes just one type FDs with just one type parameter are called ATs :) (FDs = functional dependencies, ATs is a new feature of ghc 6.8/6.10) Sorry for asking, but I tried to read 6.10 extension documentation in user's guide, as well as release notes for 6.10 and 6.8, and could not figure out what exactly are ATs. Can you give me a direction? Thanks, Maurício ___ 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] Statically dimension-checked hmatrix
Hi, What is the situation regarding statically dimension-checked linear algebra libraries? It seems that Frederik Eaton was working on one in 2006 (see the paper Statically typed linear algebra in Haskell), and he produced the Vectro library from this, based on GSLHaskell. Are there any more recent efforts into this, particularly using the new TFs? If not, I might have a go at it, as a thin wrapper for hmatrix. Cheers, Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Getting rid of functional dependencies with type proxies
On Thu, Nov 13, 2008 at 9:09 PM, Tobias Bexelius [EMAIL PROTECTED] wrote: Hi, some time ago I asked about a problem I had with functional dependencies conflicting when using overlapping instances in a code like this: {-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances -fallow-incoherent-instances #-} data V2 a = V2 a a class Vec v a where dot :: v a - v a - a instance Num a = Vec V2 a where V2 a1 a2 `dot` V2 b1 b2 = a1*b1+a2*b2 class Mult a b c | a b - c where (*.) :: a - b - c instance (Num x) = Mult x x x where (*.) = (*) instance (Vec a x) = Mult (a x) (a x) x where (*.) = dot {- Functional dependencies conflict between instance declarations: instance [overlap ok] (Num x) = Mult x x x instance [overlap ok] (Vec a x) = Mult (a x) (a x) x -} The problem here is that the dependency check is occuring too soon. Removing the dependency would solve the problem, but then you would need to put type annotations everywhere you use the multiplication operator, and that's not acceptable. However, I did found a solution I would like to share with you: Creating a type proxy! I find it strange that such a simple solution to such a (for me at least) common problem hasn't been documented more. This is the working code: {-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances -fallow-incoherent-instances #-} data V2 a = V2 a a class Vec v a where dot :: v a - v a - a instance Num a = Vec V2 a where V2 a1 a2 `dot` V2 b1 b2 = a1*b1+a2*b2 class Mult a b c | a b - c where (*.) :: a - b - c class MultProxy a b c where (*..) :: a - b - c instance MultProxy a b c = Mult a b c where (*.) = (*..) instance (Num x) = MultProxy x x x where (*..) = (*) instance (Vec a x) = MultProxy (a x) (a x) x where (*..) = dot Thanks to Emil Axelsson that pointed me to http://haskell.org/haskellwiki/GHC/AdvancedOverlap, where similar problems where discussed. Again, I haven't found links to this page in any of the Haskell tutorials I've read so far. /Tobias ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Hi, I'm not convinced your solution actually preserves the fundeps as you might expect. What I've taken to test the fundeps have been the following two functions: (of course, we need the following extensions to have sensible type inference) {-# OPTIONS -fglasgow-exts #-} {-# LANGUAGE NoMonomorphismRestriction #-} foo x y = x *. y where _ = x * y The _ = x * y clause ensures that x's type has a Num constraint. Depending on the setup, different types will be inferred by GHCi for foo. Consider your initial code, which didn't working because of conflicting instances. If you remove the (Vec a x)=... instance, then the code compiles. With the fundeps, then foo's type is inferred as foo :: Num a = a - a - a However, with your new Proxy-based code, foo's type is inferred as foo :: (Num a, MultProxy a a c) = a - a - c so some of the fundep information has been lost, in some sense. If you will consider using type equality constraints (which come with GHC 6.10) then there is another solution which I personally find more understandable than the fundeps/proxies approach. Write the classes as class Mult a b c where (*.) :: a - b - c instance (x ~ y, Num x) = Mult x x y where (*.) = (*) instance (x ~ y, Vec a x) = Mult (a x) (a x) y where (*.) = dot (Note that this doesn't require UndecidableInstances.) What's intuitively going on here is that the equality constraint in the instances acts similarly to a fundep (in that, if x is determined, then y is determined), but it's like a fundep /within the instance/. Thus, there is no conflicting instances problem, yet the fundep-like more-precise inference still works once we've selected an instance. Note that we do need to select an instance first; this requires IncoherentInstances, which you had in your code anyway. As long as IncoherentInstances is enabled, then foo's type is inferred as foo :: Num a = a - a - a as required. As I said, I personally find type equality constraints much easier to reason about than fundeps, so I like using them for this kind of problem. Cheers, Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell syntax inside QuasiQuote
I've tried it out and it looks good so far. I had to fiddle with haskell-src-ext's .cabal file to get it to install with GHC 6.10, which is surprising since it isn't listed as a broken package... ah well. I'm able to write code like this now: foo x = [$vec|sin x, myFunc x, 4*5|] Since Haskell expressions are not the entire grammar, I'm actually making a very simple parsec lexer/bracket-counter whose sole purpose is to find where the haskell expression stops (at a comma). This lexer then just passes the string verbatim onto parseExp. Unfortunately, I've uncovered a problem in the parser. For instance, with your module, [$hs|1+1*2|] evaluates to 4 rather than 3. This seems to be a general problem with infix operators, which I believe arises since haskell-src-exts isn't given the fixity declarations for + and *, so it doesn't know to bind (*) tighter than (+). I don't see how this problem can even be resolved without modifying Template Haskell: given that the operators reside in user code, there is no way to find their fixity. Cheers, Reiner On Mon, Oct 27, 2008 at 12:22 AM, Matt Morrow [EMAIL PROTECTED] wrote: I've just uploaded an alpha version of the translation to hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/haskell-src-meta-0.0.1 (I starting thinking after I uploaded that maybe haskell-src-th is a better name..) Here's one strategy for a haskell QQ: module HsQQ where import Language.Haskell.Meta import Language.Haskell.TH.Lib import Language.Haskell.TH.Quote import Language.Haskell.TH.Syntax -- | -- ghci [$hs|\x - (x,x)|] 42 -- (42,42) -- ghci (\[$hs|a@(x,_)|] - (a,x)) (42,88) -- ((42,88),42) hs :: QuasiQuoter hs = QuasiQuoter (either fail transformE . parseExp) (either fail transformP . parsePat) transformE :: Exp - ExpQ transformE = return transformP :: Pat - PatQ transformP = return I'll post updates as I add to the pkg over the next few days. Cheers, Matt On 10/21/08, Reiner Pope [EMAIL PROTECTED] wrote: It sounds like you're doing exactly what I'm looking for. I look forward to more. Reiner On Tue, Oct 21, 2008 at 4:28 PM, Matt Morrow [EMAIL PROTECTED] wrote: Is there a simple way to do this, i.e. using existing libraries? Yes indeed. I'll be traveling over the next two days, and am shooting for a fully functional hackage release by mid next week. What I need is a Haskell expression parser which outputs values of type Language.Haskell.TH.Syntax.QExp, but I can't see one available in the TH libraries, or in the haskell-src(-exts) libraries. My strategy is to use the existing haskell-src-exts parser, then translate that AST to the TH AST. Once I've got settled in one place, I'll follow up with a brain dump :) Cheers, Reiner Matt ___ 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] Haskell syntax inside QuasiQuote
On Tue, Oct 28, 2008 at 9:44 PM, Niklas Broberg [EMAIL PROTECTED] wrote: On Tue, Oct 28, 2008 at 7:56 AM, Reiner Pope [EMAIL PROTECTED] wrote: I've tried it out and it looks good so far. I had to fiddle with haskell-src-ext's .cabal file to get it to install with GHC 6.10, which is surprising since it isn't listed as a broken package... ah well. Care to tell me what the problem is? I have no problem installing it with GHC 6.10, in fact the 0.3.9 version on hackage was uploaded solely to have it compile with both old and new GHC. Running cabal install haskell-src-exts gave Resolving dependencies... 'haskell-src-exts-0.3.9' is cached. Configuring haskell-src-exts-0.3.9... Preprocessing library haskell-src-exts-0.3.9... Building haskell-src-exts-0.3.9... Language/Haskell/Exts/Syntax.hs:102:7: Could not find module `Data.Data': it is a member of package base, which is hidden cabal: Error: some packages failed to install: haskell-src-exts-0.3.9 failed during the building phase. The exception was: exit: ExitFailure 1 I am using GHC 6.10.0.20081007. Modifying the dependencies in the haskell-src-exts.cabal file to if flag(splitBase) Build-Depends: base == 4.*, array = 0.1, pretty = 1.0 allows it to compile. Unfortunately, I've uncovered a problem in the parser. For instance, with your module, [$hs|1+1*2|] evaluates to 4 rather than 3. This seems to be a general problem with infix operators, which I believe arises since haskell-src-exts isn't given the fixity declarations for + and *, so it doesn't know to bind (*) tighter than (+). I don't see how this problem can even be resolved without modifying Template Haskell: given that the operators reside in user code, there is no way to find their fixity. Yes, you're right, haskell-src(-exts) does not handle fixity of operators for you. You need to collect the fixities yourself and make a second pass over expressions to get them right. This is definitely functionality I would like to see available in haskell-src-exts (though not on by default), so if anyone were to implement it I would gladly accept patches. The problem in the case of quasi-quoting is worse than this, though. I create my quasiquoter library, and it will parse Haskell syntax including infix operators. A user may then write, eg (*+*) = undefined infixr *+* foo = [$hs|5*+*4+3|] The hs quasiquoter has no way of knowing *+*'s fixity, and template haskell provides no way to find out, as far as I know. The quasiquoter's parser only has access to the string, 5*+*4+3. Cheers, Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal and GHCi
On Tue, Oct 28, 2008 at 2:23 PM, Don Stewart [EMAIL PROTECTED] wrote: reiner.pope: Hi, Is there a way to use GHCi with code which is cabal-buildable but not ghc --make-able? The emacs haskell-mode makes a pretty good guess by :cd-ing into the directory with the .cabal file; however, if there is a different source-dir this doesn't work so well. A number of more advanced cabal features are even harder to handle. Not currently. Duncan's interested in implementing this, so if you add a tacket for a 'cabal ghci' mode, that loads up the main-is target in ghci, with all the appropriate flags, he might well implement it :-) -- Don Done: http://hackage.haskell.org/trac/hackage/ticket/382 :-) Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Cabal and GHCi
Hi, Is there a way to use GHCi with code which is cabal-buildable but not ghc --make-able? The emacs haskell-mode makes a pretty good guess by :cd-ing into the directory with the .cabal file; however, if there is a different source-dir this doesn't work so well. A number of more advanced cabal features are even harder to handle. Cheers, Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell syntax inside QuasiQuote
It sounds like you're doing exactly what I'm looking for. I look forward to more. Reiner On Tue, Oct 21, 2008 at 4:28 PM, Matt Morrow [EMAIL PROTECTED] wrote: Is there a simple way to do this, i.e. using existing libraries? Yes indeed. I'll be traveling over the next two days, and am shooting for a fully functional hackage release by mid next week. What I need is a Haskell expression parser which outputs values of type Language.Haskell.TH.Syntax.QExp, but I can't see one available in the TH libraries, or in the haskell-src(-exts) libraries. My strategy is to use the existing haskell-src-exts parser, then translate that AST to the TH AST. Once I've got settled in one place, I'll follow up with a brain dump :) Cheers, Reiner Matt ___ 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] Haskell syntax inside QuasiQuote
Hi, I have written a toy fixed-length-vector quasiquoter, so that you can write [$vec|1,2|] which has its type inferred as (Vec (S (S Z))) and you can write mkVec :: Double - Vec (S (S (S Z))) mkVec x = [$vec|1,2,x|] However, these above examples essentially demonstrate the entire syntax it supports: number literals, and anti-quoted variables. I would like to extend my quasiquoter to support Haskell's full expression syntax, so that we can write, for example, mkVec2 x = [$vec| if x 5 then sin x else cos x |] Is there a simple way to do this, i.e. using existing libraries? What I need is a Haskell expression parser which outputs values of type Language.Haskell.TH.Syntax.QExp, but I can't see one available in the TH libraries, or in the haskell-src(-exts) libraries. Thoughts? Cheers, Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hoogle? [Stacking monads]
The syntax is for the implicit parameter extension[1]. I think you would write your example as foo (undefined :: Bar x) ?z :: Bar y Then querying the type of that whole expression with :t will list ?z's type in the expression's constraints. (Of course, you should turn off the monomorphism restriction so that ghc doesn't complain if constraints aren't resolved). [1]: http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#implicit-parameters Reiner On Thu, Oct 9, 2008 at 6:11 AM, Andrew Coppin [EMAIL PROTECTED]wrote: Ryan Ingram wrote: There is such a tool, it's called ghci :) It just takes a bit of massaging to do what you want: ghci :set -fglasgow-exts ghci :t (?f some_func [?a .. ?b]) Here's an example: Prelude :t ?f map [?a .. ?b] ?f map [?a .. ?b] :: forall t a b t1. (Enum t1, ?b::t1, ?a::t1, ?f::((a - b) - [a] - [b]) - [t1] - t) = t This tells you the types the variables have to have, and the type of the expression. Judicious use of (undefined :: type_signature) can also help. Using undefined is already a standard technique for me. But what it doesn't let you do is foo (undefined :: Bar x) (undefined) :: Bar y -- What type is the second argument? I'm curios as to how the example you give actually works - I don't recognise that syntax at all... ___ 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] Re: having fun with GADT's
Anatoly Yakovenko aeyakovenko at gmail.com writes: I dont remember where i saw it, but i think someone had an example of a list whose type is the maximum element in the list. I've been trying to reproduce that with GADT's. data One = One data Two = Two data Three = Three data MaxList t where Elem1 :: MaxList One Elem2 :: MaxList Two ML1Cons1 :: MaxList One - MaxList One - MaxList One ML1Cons2 :: MaxList One - MaxList Two - MaxList Two ML2Cons1 :: MaxList Two - MaxList One - MaxList Two ML2Cons2 :: MaxList Two - MaxList Two - MaxList Two a = ML2Cons2 Elem2 $ ML2Cons1 Elem2 $ ML1Cons1 Elem1 $ Elem1 so one problem is the tedium of defining a cons for each possible combination. The other problem is that i cant define a usefull tail that makes any sense. mlTail :: MaxList Two - MaxList t mlTail (ML2Cons2 a b) = b mlTail (ML2Cons1 a b) = b this one doesn't work, and probably because there is nothing that i could do with the return value. Your problem in this example is that the t in MaxList t is universally quantified when it needs to be existentially quantified. The following definition encodes the existential quantification as a rank-2 type: mlTail :: MaxList n - (forall t. MaxList t - a) - a mlTail (ML1Cons1 h t) f = f t mlTail (ML1Cons2 h t) f = f t mlTail (ML2Cons1 h t) f = f t mlTail (ML2Cons2 h t) f = f t It works with the rest of your code unmodified. mlTail :: MaxList Two - MaxList Two mlTail (ML2Cons2 a b) = b mlTail (ML2Cons1 a b) = b --wont compile because b is a MaxList One will only work for lists that only contain Two's, which is not what i want either. So is this somehow possible? This example here suggests that you are happy merely with a (not necessarily tight) upper bound on the list elements. The following code solves your problem in this case, using only type unification and not fundeps or TFs: data Nat a where Z :: Nat a S :: Nat a - Nat (S a) data Z data S a n00 = Z n01 = S n00 n02 = S n01 n03 = S n02 n04 = S n03 data MaxList t where Nil :: MaxList a Cons :: Nat a - MaxList a - MaxList a a = Cons n02 $ Cons n02 $ Cons n01 $ Nil --- :t a gives forall a. MaxList (S (S a)) which tells you exactly --- what you want: elements are at least 2. mlTail :: forall t. MaxList t - MaxList t mlTail (Cons h t) = t --- unfortunately, you lose information here if the first --- element is larger than the rest. Reiner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe