Re: [Haskell-cafe] ghc overlapping instances - solved
Hello,
Isaac, this works for me.
Thx a lot,
Steffen
2007/12/5, Isaac Dupree [EMAIL PROTECTED]:
Steffen Mazanek wrote:
Hi,
Stefan and Isaac, thx for providing quick advice.
@Stefan: Unfortunately I have to use a list.
@Isaac: I do not get it. Could you please provide a short example of
your
approach?
The question still remains. Which arguments do I have ghc to start with
to
get the same behavior than hugs with -98 +o (here it works).
I provide my example for testing purposes:
module Test where
import Test.QuickCheck
import Monad(liftM,liftM2)
type Program = [Stmt]
data Stmt = Text | IfElse Program Program | While Program deriving (Eq,
Show)
instance Arbitrary [Stmt] where
arbitrary = sized genProg
instance Arbitrary Stmt where
arbitrary = sized genStmt
genStmt::Int-Gen Stmt
genStmt 0 = return Text
genStmt 1 = return Text
genStmt 2 = oneof [return Text, return (While [Text])]
genStmt n | n2 = oneof ([return Text,
liftM While (genProg (n-1))]++
[liftM2 IfElse (genProg k) (genProg
(n-k-1))|k-[1..n-2]])
genProg::Int-Gen Program
genProg 0 = return []
genProg 1 = return [Text]
genProg n | n1 = oneof ((liftM (\x-[x]) (genStmt n)):[liftM2 (:)
(genStmt
k) (genProg (n-k))|k-[1..n-1]])
prop_ConstructParse progr = True
where types = progr::Program
main = mapM_ (\(s,a) - putStrLn s a) [(flowchart construct and
parse,
test prop_ConstructParse)]
is prop_ConstructParse the only thing that breaks when you remove the
instance Arbitrary [Stmt] where arbitrary = sized genProg, or have I
missed something? If that's all, try this (untested) :
prop_ConstructParse = forAll (sized genProg) (\progr - True)
and similarly for other properties.
Or, you _can_ use a newtype for quickcheck-only, something like this:
newtype P = P { unP :: Program }
instance Show P where show = show . unP
instance Arbitrary P where arbitrary = sized genProg . unP
prop_ConstructParse (P progr) = True
Isaac
--
Dipl.-Inform. Steffen Mazanek
Institut für Softwaretechnologie
Fakultät Informatik
Universität der Bundeswehr München
85577 Neubiberg
Tel: +49 (0)89 6004-2505
Fax: +49 (0)89 6004-4447
E-Mail: [EMAIL PROTECTED]
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ghc overlapping instances
Hi, Stefan and Isaac, thx for providing quick advice. @Stefan: Unfortunately I have to use a list. @Isaac: I do not get it. Could you please provide a short example of your approach? The question still remains. Which arguments do I have ghc to start with to get the same behavior than hugs with -98 +o (here it works). I provide my example for testing purposes: module Test where import Test.QuickCheck import Monad(liftM,liftM2) type Program = [Stmt] data Stmt = Text | IfElse Program Program | While Program deriving (Eq, Show) instance Arbitrary [Stmt] where arbitrary = sized genProg instance Arbitrary Stmt where arbitrary = sized genStmt genStmt::Int-Gen Stmt genStmt 0 = return Text genStmt 1 = return Text genStmt 2 = oneof [return Text, return (While [Text])] genStmt n | n2 = oneof ([return Text, liftM While (genProg (n-1))]++ [liftM2 IfElse (genProg k) (genProg (n-k-1))|k-[1..n-2]]) genProg::Int-Gen Program genProg 0 = return [] genProg 1 = return [Text] genProg n | n1 = oneof ((liftM (\x-[x]) (genStmt n)):[liftM2 (:) (genStmt k) (genProg (n-k))|k-[1..n-1]]) prop_ConstructParse progr = True where types = progr::Program main = mapM_ (\(s,a) - putStrLn s a) [(flowchart construct and parse, test prop_ConstructParse)] 2007/12/4, Stefan O'Rear [EMAIL PROTECTED]: On Tue, Dec 04, 2007 at 03:36:20PM +0100, Steffen Mazanek wrote: Hello, I want to quickcheck a property on a datatype representing programs (=[Stmt]) and need to define a specific instance instance Arbitrary [Stmt] (mainly to restrict the size of the list). In quickcheck an instance Arbitrary of lists is already defined. Which parameters do I have to give ghc such that it accepts such an instance? In hugs -98 +o is enough. I have tried -XOverlappingInstances, -XFlexibleInstances and also -XIncoherentInstances, however I still got an overlapping instances error for this declaration. You shouldn't use lists if you need to have special instance behavior - lists are for perfectly ordinary sequences of things. If a program is just a bunch of unrelated statements, then use [], otherwise use a custom (new)type. Stefan -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFHVcxTFBz7OZ2P+dIRAmtMAJ9xcL0xhG9u+QaIFXwhEEq177ePEgCfUfOf dlDMHAN8ldq2qZ7ctOFkNb4= =hxkS -END PGP SIGNATURE- -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ghc overlapping instances
Hello, I want to quickcheck a property on a datatype representing programs (=[Stmt]) and need to define a specific instance instance Arbitrary [Stmt] (mainly to restrict the size of the list). In quickcheck an instance Arbitrary of lists is already defined. Which parameters do I have to give ghc such that it accepts such an instance? In hugs -98 +o is enough. I have tried -XOverlappingInstances, -XFlexibleInstances and also -XIncoherentInstances, however I still got an overlapping instances error for this declaration. Regards, Steffen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] standard function
Hello, is there a function f::[a-b]-a-[b] in the libraries? Couldn't find one using hoogle although this seems to be quite a common thing... Steffen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: standard function
Cool! Haskell surprised me once again :) @Paul: Thank you for pointing me to the old thread. @Neil: Is there a way to let hoogle find this kind of stuff? It would be a quite complex inference though. 2007/6/6, apfelmus [EMAIL PROTECTED]: Steffen Mazanek wrote: is there a function f::[a-b]-a-[b] in the libraries? There is, it's called 'sequence' :) You need to import Control.Monad.Instances though, to get the famous reader monad ((-) a). Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: CYK-style parsing and laziness
Note that there are very systematic and natural ways to derive dynamic programming algorithms in functional languages. In a sense, much of the work of R. Bird centers this topic. The book Algebra of Programming http://web.comlab.ox.ac.uk/oucl/research/pdt/ap/pubs.html#Bird-deMoor96:Algebra is one of the cornerstones. The systematic derivation of dynamic programming algorithms has been rediscovered in a more direct but less general fashion http://bibiserv.techfak.uni-bielefeld.de/adp/ Thanks a lot for providing the links! Interesting stuff! And also many thanks for the examplary implementation. This is really enlightening. Ciao, Steffen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] CYK-style parsing and laziness
Hello, I have two questions regarding a Cocke, Younger, Kasami parser. Consider this program: type NT = Char -- Nonterminal type T = Char -- Terminal -- a Chomsky production has either two nonterminals or one terminal on its right-hand side type ChomskyProd = (NT, Either T (NT, NT)) -- a grammar consists of a startsymbol, nonterminal symbols, terminal symbols and productions type Grammar = (NT, [NT], [T], [ChomskyProd]) parse::Grammar-[T]-Bool parse (s, nts, ts, prods) w = s `elem` gs n 1 where n = length w table = [[gs i j|j-[1..n-i+1]]|i-[1..n]] gs 1 j = [nt|p-prods,termProd p, let (nt, Left t)=p, w!!(j-1)==t] gs i j = [nt|k-[1..i-1],p-prods, not (termProd p), let (nt, Right (a, b))=p, a `elem` table!!(k-1)!!(j-1), b `elem` table!!(i-k-1)!!(j+k-1)] The sets gs i j contain all nonterminal symbols from which the substring of w starting at index j of length i can be derived. Please have a look at the last line of the algorithm. In my first attempt I just referred to gs k j and gs (i-k) (j+k) what looks a lot more intuitive. However I noted that this way the sets gs i j are evaluated multiple times. Is there a better and more readable way to prevent multiple evaluation of these sets? The second question regards lazy evaluation. Consider the stupid grammar S-S S S-A A A-a that generates a^(2n). The performance of the algorithm drops very fast even for small n, probably because the gs i j are getting very large. Is there a trick to get lazy evaluation into play here? It is sufficient to find only one occurence of the start symbol in gs n 1. Best regards, Steffen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: CYK-style parsing and laziness
Once again thank you apfelmus :-) The key point of the dynamic programming algorithm is indeed to memoize the results gs i j for all pairs of i and j. In other words, the insight that yields a fast algorithm is that for solving the subproblems gs i j (of which there are n^2), solution to smaller subproblems of the same form are sufficient. Tabulation is a must. I understand this, however I thought it would be possible to use the automatic collapsing of the termgraphs in some way. Of course, you can still choose how to represent the table. There's a nice higher order way to do that tabulate :: (Int - Int - a) - (Int - Int - a) gs = tabulate gs' where gs' 1 j = ... uses gs x y for some x y ... gs' i j = ... ditto ... Thank you for this explanation. Your approach is not very concise either but it does not pollute the algorithm so much. That would be strange. I mean, no gs i j may have more than two elements, namely S or A. The other key point of the CYK algorithm is that the sets gs i j are indeed sets and may only contain as many elements as there are nonterminals. ... You are right, of course. I have tried a nub before the list comprehension however this is evaluated too late. I should really use sets, however, I would miss the list comprehension syntactic sugar sooo much. Is there something similar for real Data.Set? Best regards, Steffen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List algorithm
Thank you for your responses. My algorithm that needs the described function performs so horribily bad that I understand now the need for CNF :-) The idea was to write a CYK-style parser for an arbitrary context-free grammar without transformation to CNF. To compute derivations for a span of length i I wanted to iterate over all productions p, counting the number n of Nonterminals at the right-hand side of p, computing all lists with n numbers whose sum is i and split the span accordingly. It works, however, the strings have to be very, very short *g* Ciao and Thx, Steffen 2007/5/22, Jules Bean [EMAIL PROTECTED]: Matthew Brecknell wrote: This seems to work, but presumably only because it's a boxed array, and the construction makes no circular references. Yes, AIUI the boxed arrays are strict in indices but lazy in values. Therefore they can be used for this kind of memoization trick as long as you're access the elements in 'some sensible order' (that is the calculation dependencies are well-ordered). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] List algorithm
Hello, is there an efficient algorithm that takes two positive numbers n and m and that computes all lists l of numbers 0x=n such that sum l = m? For instance alg 5 1 = [[1]] alg 5 2 = [[1,1],[2]] alg 5 3 = [[1,1,1],[1,2],[2,1],[3]] ... I know that filter (\l-sum l == m) (powerSet [1..n]) would do the job, however I am looking for a more efficient approach. Help is greatly appreciated, even a google search term would be fine :-) I really hope for a polynomial algorithm although I am not very optimistic about this. Ciao, Steffen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Profiling, measuring time
Thats it! Thanks a lot. I do not even need forceOutput, because I perform a bottom-up analysis. And the timeline I got looks sooo great (perfect polynomial behavior :-)) Best regards, Steffen 2007/5/20, Matthew Brecknell [EMAIL PROTECTED]: Steffen Mazanek: I have written a function f, that performs a quite complex operation on its argument. Furthermore I have another function genInput that takes a number and constructs an argument for f of this size. What I want now is a list [(n,time)] that gives me for every size of input n the time, f needs to compute this input. How can I do this? I have found the module Time and tried diffClockTimes, but I ever got zero as a delta. Lazy evaluation makes it tricky to measure exactly the computation you want to measure. You are probably measuring the time it takes to construct a single unevaluated thunk on the heap. If that's the case, you need to add strictness annotations to force the computation you want to measure. However, you need to take care to ensure that: (a) the entire computation you want to measure is forced between your start/stop timer samples, and (b) no other computations are incidentally forced between your start/stop timer samples. So, given a pure function f :: Input - Output, you can write (untested): import System.CPUTime ftimer :: Int - IO Integer ftimer n = do input - return $! forceInput $ genInput n -- (b) t0 - getCPUTime return $! forceOutput $ f input -- (a) t1 - getCPUTime return (t1-t0) I've marked the lines which (I think) ensure the conditions described above. Note the use of return $! to sequence the pure computations at the appropriate points in the IO computation. The purpose of the forcing functions (forceInput :: Input - Input) and (forceOuput :: Output - Output) is to ensure there are no unevaluated thunks in values of type Input and Output, respectively. This is necessary because seq only forces values to Weak Head Normal Form (WHNF), which means it only goes as far as the top-level data constructor. The implementations of these functions will depend on the definitions of those types, so you'll need to give more details of the types if you want help with that. Here are some (untested) examples of forcing functions to get you started. -- Forcing a trivial data type is a no-op. forceInt :: Int - Int forceInt = id -- To force a list, force both the spine and the values. forceIntList :: [Int] - [Int] forceIntList l = foldr seq l l -- Some data types for illustration. data Foo = Foo Int Bar Baz data Bar = Bar Int data Baz = Baz !Int -- Forcing evaluation inside a data constructor. forceBar :: Bar - Bar forceBar b@(Bar i) = i `seq` b -- This has already been forced by the strictness annotation in the data definition. forceBaz :: Baz - Baz forceBaz = id -- Elide forceInt and forceBaz, since they are no-ops. forceFoo :: Foo - Foo forceFoo f@(Foo i b z) = i `seq` forceBar b `seq` z `seq` f -- This time, forcing the list values is non-trivial. forceFooList :: [Foo] - [Foo] forceFooList = forceGenericList forceFoo -- To force lists generically, we need to be told how to force the values. forceGenericList :: (a - a) - [a] - [a] forceGenericList vf l = foldr (seq.vf) l l I hope that helps. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Profiling, measuring time
Hello, I have written a function f, that performs a quite complex operation on its argument. Furthermore I have another function genInput that takes a number and constructs an argument for f of this size. What I want now is a list [(n,time)] that gives me for every size of input n the time, f needs to compute this input. How can I do this? I have found the module Time and tried diffClockTimes, but I ever got zero as a delta. Help is greatly appreciated. There is probably a way to do this via ghcs profiling but I hope that there is also a normal Haskell way of doing this. Best regards, Steffen -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generate Haskell code from model
Hi Neil, It sounds a lot to me like: * Create a visual meta-language * Program with diagrams * Translate to Haskell Yes, that is true and I guess this is a standard procedure, isn't it? The translation process is not at all different from your Translate to C++. The difference is the Visual Language. It is hard to understand a program just by reading the code. An easy to understand visual notation can ease the understandability of your programs. Nowadays there are so many tools out there, that it is very easy to implement such a visual language. A decade ago there already was research in this direction, however, it was pretty make a good tool-oriented. Today we could tackle the visual notation with all forces and get the tool support for free (nearly). For example, the notion of a package diagram is for Haskell as useful as for OOP languages, because it can help you to understand the overall structure of a program. On a deeper level you could plug together a visual language for type class hierarchies (similar to but of course not equivalent to class diagrams), a type-construction-language and what else comes to your mind and get a Haskell CASE tool. The problem of modeling+editing is nearly solved in the OOP world (see FUJABA for instance or EMFs JMerge). openArchitectureWare lets you define protected regions for this purpose - a very general approach that is not so good for readability. You say Haskell is good for implementing DSLs, yeah, than it will be no problem to define a DSL for itself :-) Ciao, Steffen If thats the case, how is Translate to Haskell different from Translate to C++? It only makes a difference if you go in and edit the result, but then you've lost your model? The other thing is that defining a domain specific language is well understood in Haskell, and generally looks quite nice. The advantage is that it can integrate with the rest of Haskell easily - if you take away the Haskell and move into the realm of models I don't see how you can keep this selling point. (Personal note: I detest modelling languages with a passion, and I love Haskell with a passion - I'm curious whether I love or hate the combination) Thanks Neil On 5/9/07, Steffen Mazanek [EMAIL PROTECTED] wrote: I have done some experiments relating to our discussion. The approach to generate Haskell code from UML class diagrams is not very promising. However one may define a visual notation of Haskell (this is no new idea of course), provide better tool support (in particular editor+code generator) and pull the Haskellers away from vim, emacs or even from the Visual Studio Plugin Visual Haskell, that is more a Haskell IDE Integration than a visual programming environment (great work either way!). I have described a possible toolchain towards a real Visual Haskell at my blog: http://www.steffen-mazanek.de/blog/2007/05/visual-language-howto.html Best regards, Steffen 2007/4/14, Brian Smith [EMAIL PROTECTED]: On 4/14/07, Steffen Mazanek [EMAIL PROTECTED] wrote: Brian, but don't you think that you have to write a lot of boilerplate code in Haskell? I have never felt I was writing a lot of boilerplate. There are a lot of abstraction mechanisms in Haskell to avoid boilerplate. Second, if Haskell should be more successful in the real world there has to be a way of demonstrating basic ideas of a big program to customers. How would you do this? Everybody knows UML class diagrams, for example. In contrast, nobody knows about termgraphs or lambda *g*. I've never had to show a UML or ER diagram to any business people--usually they want a slideshow that is far simpler and a little prettier. The fact that nobody knows about termgraphs or lambda in your group means that you probably shouldn't be considering Haskell (for the same reason my bosses always asked me to document everything--in case you get hit by a bus). Thank you very much for contributing to the discussion. Please assume, that you have to generate the code from a model. Further assume, that you have no choice and are not allowed to discuss the sense of this approach :-) How should the code look like? I am not sure if you are trying to solve a real problem or not. If you are solving a real problem, where you already happen to have an EMF model which you are required to generate code from, then I recommend to just do everything in Java using the existing tools built for EMF. If you decide to still keep working in Haskell, and it works out well, please share your solution because I think many people here will be very interested. wxHaskell, OOHaskell, and O'Haskell are all starting points for this type of project. - Brian -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED
Re: [Haskell-cafe] generate Haskell code from model
I have done some experiments relating to our discussion. The approach to generate Haskell code from UML class diagrams is not very promising. However one may define a visual notation of Haskell (this is no new idea of course), provide better tool support (in particular editor+code generator) and pull the Haskellers away from vim, emacs or even from the Visual Studio Plugin Visual Haskell, that is more a Haskell IDE Integration than a visual programming environment (great work either way!). I have described a possible toolchain towards a real Visual Haskell at my blog: http://www.steffen-mazanek.de/blog/2007/05/visual-language-howto.html Best regards, Steffen 2007/4/14, Brian Smith [EMAIL PROTECTED]: On 4/14/07, Steffen Mazanek [EMAIL PROTECTED] wrote: Brian, but don't you think that you have to write a lot of boilerplate code in Haskell? I have never felt I was writing a lot of boilerplate. There are a lot of abstraction mechanisms in Haskell to avoid boilerplate. Second, if Haskell should be more successful in the real world there has to be a way of demonstrating basic ideas of a big program to customers. How would you do this? Everybody knows UML class diagrams, for example. In contrast, nobody knows about termgraphs or lambda *g*. I've never had to show a UML or ER diagram to any business people--usually they want a slideshow that is far simpler and a little prettier. The fact that nobody knows about termgraphs or lambda in your group means that you probably shouldn't be considering Haskell (for the same reason my bosses always asked me to document everything--in case you get hit by a bus). Thank you very much for contributing to the discussion. Please assume, that you have to generate the code from a model. Further assume, that you have no choice and are not allowed to discuss the sense of this approach :-) How should the code look like? I am not sure if you are trying to solve a real problem or not. If you are solving a real problem, where you already happen to have an EMF model which you are required to generate code from, then I recommend to just do everything in Java using the existing tools built for EMF. If you decide to still keep working in Haskell, and it works out well, please share your solution because I think many people here will be very interested. wxHaskell, OOHaskell, and O'Haskell are all starting points for this type of project. - Brian -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: Quicksearch vs. lazyness
Hello, ok, but this still means, that you have to rewrite the algorithm to get an efficient qsearch for arbitrary k. Are there any popular algorithms whose overall complexity is improved by lazyness? Or where you get such special cases as free lunch? Such an algorithm could be useful as a motivating example of Haskell for the talk at the open source conference (that is currently discussed at haskell-cafe). These people are mostly really excited about performance :-) Best regards, Steffen Apparently, I did not think enough about quicksort :) as it is well capable of delivering the minimum element in O(n) time. In fact, given proper pivot choice, take k . qsort is the optimal O(n + k log k) algorithm for returning the first k smallest elements in sorted order! See also http://en.wikipedia.org/wiki/Selection_algorithm Let's assume that the quicksort in qsort [] = [] qsort (x:xs) = qsort ls ++ [x] ++ qsort rs where ls = filter ( x) xs rs = filter (= x) xs always uses a good pivot x, i.e. that ls and rs have around n/2 elements each. As long as this n/2 is greater than k, taking the first k elements does not evaluate the second recursive call to quicksort. In other words, it takes O(n) -- for filtering xs during the initial call to qsort + O(n/2) -- same as above but with the first half of the list + O(n/4) -- filtering the half of the half + ... + O(k) O(n + n/2 + n/4 + n/8 + ...) = O(n) time until ls has fewer than k elements. When this becomes the case, the argument list to the recursive call to qsort has a size of at most 2*k and it takes at most O(k log k) time finish sorting it completely and taking the first k elements of this. This gives a total of O(n + k log k). Regards, apfelmus ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Tutorial on Haskell
What about demonstrating the use of an Haskell interpreter as a pimped up calculator? multTable = putStr $ unlines [unlines [show x ++ ' ':show y ++ ' ':show (x*y)|y-[1..10]] | x-[1..10]] 2007/4/16, Simon Peyton-Jones [EMAIL PROTECTED]: Friends I have agreed to give a 3-hr tutorial on Haskell at the Open Source Convention 2007 http://conferences.oreillynet.com/os2007/ I'm quite excited about this: it is a great opportunity to expose Haskell to a bunch of smart folk, many of whom won't know much about Haskell. My guess is that they'll be Linux/Perl/Ruby types, and they'll be practitioners rather than pointy-headed academics. One possibility is to do a tutorial along the lines of here's how to reverse a list, here's what a type is etc; you know the kind of thing. But instead, I'd prefer to show them programs that they might consider *useful* rather than cute, and introduce the language along the way, as it were. So this message is to ask you for your advice. Many of you are exactly the kind of folk that come to OSCON --- except that you know Haskell. So help me out: Suggest concrete examples of programs that are * small * useful * demonstrate Haskell's power * preferably something that might be a bit tricky in another language For example, a possible unifying theme would be this: http://haskell.org/haskellwiki/Simple_unix_tools Another might be Don's cpu-scaling example http://cgi.cse.unsw.edu.au/~dons/blog/2007/03/10 But there must be lots of others. For example, there are lots in the blog entries that Don collects for the Haskell Weekly Newsletter. But I'd like to use you as a filter: tell me your favourites, the examples you find compelling. (It doesn't have to be *your* program... a URL to a great blog entry is just fine.) Of course I'll give credit to the author. Remember, the goal is _not_ explain monads. It's Haskell is a great way to Get The Job Done. Thanks! Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] generate Haskell code from model
Hello everybody,
I would like to start a discussion on how to generate
best-practice Haskell code from a model, e.g. from
EMF.
It seems to be very difficult and unconvenient to simulate
OOP with Haskell (as described in the paper Object-oriented
style overloading for Haskell). However, I think it might
be possible to generate something useful out of a model to
not start from scratch an implementation.
For example, I could imagine to generate for every class
a module, import and export lists and a type class (with some
restrictions) at the very least.
In the EMF book there is an example, PurchaseOrder, look at
http://www.awprofessional.com/content/images/0131425420/samplechapter/budinskych02.pdf
at page 11.
How would you like generated code from this model to look like?
The most obvious way would be something like this:
data PurchaseOrder = PurchaseOrder {shipTo::String, billTo:: String,
items::[Item]}
data Item = Item {productName::String, quantity::Int, price::Float}
This does not work well if function names are reused or
inheritance comes into play, however, even this might be a useful
starting point (better than nothing).
The benefits of the model+generate approach are well known. Best practices
in programming are propagated, for Haskell e.g. use different modules
for different things, use the tedious import/export lists, Haddock your
code...
What are your ideas?
Best regards,
Steffen
--
Dipl.-Inform. Steffen Mazanek
Institut für Softwaretechnologie
Fakultät Informatik
Universität der Bundeswehr München
85577 Neubiberg
Tel: +49 (0)89 6004-2505
Fax: +49 (0)89 6004-4447
E-Mail: [EMAIL PROTECTED]
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generate Haskell code from model
Brian, but don't you think that you have to write a lot of boilerplate code in Haskell? Second, if Haskell should be more successful in the real world there has to be a way of demonstrating basic ideas of a big program to customers. How would you do this? Everybody knows UML class diagrams, for example. In contrast, nobody knows about termgraphs or lambda *g*. Third, assume you already have a model, want to write the corresponding code yourself? Thank you very much for contributing to the discussion. Please assume, that you have to generate the code from a model. Further assume, that you have no choice and are not allowed to discuss the sense of this approach :-) How should the code look like? Best regards, Steffen 2007/4/13, Brian Smith [EMAIL PROTECTED]: On 4/13/07, Steffen Mazanek [EMAIL PROTECTED] wrote: Hello everybody, I would like to start a discussion on how to generate best-practice Haskell code from a model, e.g. from EMF. I started learning Haskell precisely to solve problems like this. But, once I got into it, I realized that Haskell is a much better modeling language than the modeling language I was using (MOF/UML, the predecessors to EMF). Furthermore, all the infrastructure built on top of that modeling language was very easy to replace with Haskell code. As a result, I gave up that effort. You said The benefits of the model+generate approach are well known, however I disagree. W3C DOM, MOF, UML, CORBA, and NetBeans 3.x-4.x are all obvious examples of the failure of the model+generate approach. If the modeling language is sufficiently powerful, then it should be feasible to execute the models directly using a (custom-built) interpreter. If the modeling language is weak then it is better to just do the modeling in Haskell or another more powerful language. The MDA idea was that you would have one model and then be able to use that model in a variety of different programming languages, without having to rewrite code in each target language. Now, people are getting this benefit via a code, then translate approach. For example, GWT allows the developer to write Java code, then generate the equivalent Javascript, without any hand-wavy models in between. JRuby lets one write code in Ruby to be used by code in Java; IronPython does the same for other .NET languages. In fact, C# is basically the .NET counterpart to EMF. FWIW, I also think that data based languages like ERD, Relax NG, and XQuery/XPath/XML Schema are a much closer fit to Haskell than EMF. EMF is designed to be translated any object-oriented, class-based, (soley) subtype-polymorphic, single-dispatched, single-inheritance language; i.e. Java. In fact, EMF is really a Java-optimized subset of what was supposed to become part of MOF 2.0. - Brian -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generate Haskell code from model
Hi Neil, Just to say, I agree with Brian totally! I've been (violently and forcefully) exposed to MOF tools in the past, and at every turn my thought was the Haskell would be clearer, shorter and executable! This is true only for programming in the small, isn't it? Furthermore, from my point of view Haskell code is very clear if we talk about computations, in contrast the dependencies of data modelling are harder to overview. Humans just like pictures :) Not everybody is a hardcore Haskell hacker. Brian, but don't you think that you have to write a lot of boilerplate code in Haskell? Can you give an example? Usually higher order functions, monads, laziness etc can combine to make the boilerplate minimal, if not invisible. This is exactly the kind of problem haskell-cafe will excel at. I do not mean the code per se. I was talking more about structure, modules, comments, ... Haskell hackers have invented a lot of cool stuff to make their life easier, however this stuff often is complicated to understand :-) or not standard compliant. If you can generate Java code from a model, why on earth would you then want to generate Haskell code from it? I see know reason to use the assembly language called Haskell vs the assembly language called Java - since if you are compiling a model to anything, it is just serving as an assembly language. Hmph, how to disprove this argument? Say, you have generated ddl-code from an ER-model and now want to generate Haskell data structures that operate on this data. How would you procede? This is similar to HaXML that helped you to generate Haskell types for an xml schema. Best regards, Steffen -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell] Quicksearch vs. lazyness
Hello, say, we want to find the k'th element in a sorted list. In imperative languages it is much more efficient to not use quicksort first and get the k'th element later, but to use a quicksearch algorithm that sorts only the relevant parts of the array. In Haskell one could implement this idea as follows: qsearch k [] = error ... qsearch k (x:xs) | lsmaller = k = qsearch k smaller | lsmaller == 0 k 1 = qsearch (k-1) greater | lsmaller == 0 = x | otherwise = qsearch (k-lsmaller) (x:greater) where smaller = filter (= x) xs lsmaller = length smaller greater = filter ( x) xs However, I was wondering whether it might be possible to implement quicksort in a way that quicksearch is done out of the box by lazy evaluation. Is there any way to do this? From my understanding for small k's lazy evaluation already does the trick for the naive quicksort algorithm (quicksort smaller ++ [x] ++ quicksort greater), doesn't it? Is there a search algorithm that makes better use of lazy evaluation out of the box? Best regards, Steffen ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell-cafe] Re: [Haskell] Haskell Chess
Hello again, first of all, thank you Don for your help in making hsChess accessible. I have to have a look at darcs and cabal first :-) I have added some more content and a discussion page to the wiki, please contribute your thoughts. Furthermore I added a link to the german project and task description used in the exercises; the English version will be the wiki (although it has no convert2tex function). Best regards, Steffen Donald Bruce Stewart schrieb: smazanek: Hello again, I got a lot of interesting and useful comments on my posting about Haskell Chess. Somebody suggested using the program for benchmarks. Several people asked me to open the program for contributions. And others were just interested in the exercises. It is probably the best to branch the development, so that we have a teachers' and a hackers' version (ease of understanding and learning paradigms vs. efficiency and implementation of full ruleset). I will do the necessary steps next week (svn, etc). Somebody already offered help for cabalizing hsChess. hsChess has been cabalised, and is available now via darcs; darcs get http://www.cse.unsw.edu.au/~dons/code/contrib/hsChess/ You can also browse the source directly: http://www.cse.unsw.edu.au/~dons/code/contrib/hsChess/ Several people asked me for the exercises so I started the wiki page http://haskell.org/haskellwiki/Learning_Haskell_With_Chess on this topic. I will add more content when I am back to office. Every contribution and discussion is welcome. I am happy to host the code at the above url, unless Steffen, you have a better place to host the repository? -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Chess
I originally used a more general approach (probably similar to the one you refer to), but kicked generality out in favor of simplicity. In teaching one should probably just discuss this aspect, but stay with the simple approach (I'll add a note to the wiki page :-)). In contrast, for the real Haskell world such a library would be great. One could even use an abstract game specification and compute the corresponding core (if existing and computation being feasible according to the complexity of the game). Two-Player-zero-sum games are very library friendly kinds of games. However, interesting other games are probably too diverse to be pressed in a general framework, aren't they? Henning Thielemann schrieb: On Mon, 19 Mar 2007, Andrew Wagner wrote: Steffen, I've done some chess AI programming in the past, so I'd be happy to help with this project. I have some pretty fundamental design suggestions that I'll write up for the wiki page. As a spin-off, will there grow some library for general strategies in board games, like those described in why functional programming matters? ___ 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] Haskell Chess
Hello again, I got a lot of interesting and useful comments on my posting about Haskell Chess. Somebody suggested using the program for benchmarks. Several people asked me to open the program for contributions. And others were just interested in the exercises. It is probably the best to branch the development, so that we have a teachers' and a hackers' version (ease of understanding and learning paradigms vs. efficiency and implementation of full ruleset). I will do the necessary steps next week (svn, etc). Somebody already offered help for cabalizing hsChess. Several people asked me for the exercises so I started the wiki page http://haskell.org/haskellwiki/Learning_Haskell_With_Chess on this topic. I will add more content when I am back to office. Every contribution and discussion is welcome. Best regards, Steffen Steffen Mazanek schrieb: Hello, I recently implemented Chess in Haskell. The implementation is not very efficient, but pretty straightforward from a purely functional point of view. Simple mate problems can be solved. Have a look at http://www.steffen-mazanek.de/blog/2007/02/haskell-chess.html I used this implementation for Haskell exercises and the students liked it - probably because of the fact, that it is possible to write a real Chess program in about 200 lines of code. I guess implementing such a game is a good thing in Haskell didactics, in particular the game can easily be divided in several completely independent modules (board data structure and stuff, move generator, gametree and minmax algorithm), there are quick results and the students can experiment a lot. A nice thing to tell them is the fact, that many of the implemented functions are not Chess-specific at all, in particular the generation of the gametree and the application of the minimax algorithm can be easily generalized. If somebody is interested I gladly provide the used project definition and the particular work orders (in German only). Best regards, Steffen Mazanek ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Haskell Chess
Hello, I recently implemented Chess in Haskell. The implementation is not very efficient, but pretty straightforward from a purely functional point of view. Simple mate problems can be solved. Have a look at http://www.steffen-mazanek.de/blog/2007/02/haskell-chess.html I used this implementation for Haskell exercises and the students liked it - probably because of the fact, that it is possible to write a real Chess program in about 200 lines of code. I guess implementing such a game is a good thing in Haskell didactics, in particular the game can easily be divided in several completely independent modules (board data structure and stuff, move generator, gametree and minmax algorithm), there are quick results and the students can experiment a lot. A nice thing to tell them is the fact, that many of the implemented functions are not Chess-specific at all, in particular the generation of the gametree and the application of the minimax algorithm can be easily generalized. If somebody is interested I gladly provide the used project definition and the particular work orders (in German only). Best regards, Steffen Mazanek -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: steffen.mazanek (at) unibw.de ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] main::[String]-IO() ?
Hello, thank you for all the valuable comments. A main function with arguments would correspond better to the principle of the least surprise, however, you are perfectly right with your arguments, too. getArgs is not so hard to remember I guess :-) Bye, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] main::[String]-IO() ?
Hello again. Since type signature declarations for functions are generally considered good practice, those who use - getArgs would actually need to type two extra characters. And those who do not use getArgs typically (which may or may not be the case in general), would type an extra 14 characters. One might also consider getProgName and getEnv to be plausible arguments to main as they are for some variants of c. However, in this case we are getting quite excessive with main's arguments. Just a thought: is there a Haskell extensions that allows some kind of optional function arguments? Not that I want to compare Haskell and C :-) but as far as I know in C you have the choice. I could imagine that it may be possible with Template Haskell. Furthermore I see some analogies with Formatting: a class act by Ralf Hinze (as far as I understand this (and this is not so deep) value dependent types are simulated by type classes). Bye, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
[Haskell] main::[String]-IO() ?
Hello everybody, each time I write an application that makes use of command line arguments I have to copypaste the code for dealing with these args to my program from a reference implementation, because it is so hard to remember. What do you think about changing the default type of main or providing an alternative, e.g., main_args, just like in C or Java? I think this would simplify everyday-programming a lot. Or are there any severe theoretical (semantical) problems (main is running in the IO monad either way)? Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] HaXml and XML Schema
Hello, thank you for the references. Looks promising. I will read it carefully. A nice solution I really like was found by Alastair Reid. He proposed to me (hope it is ok to cite this) the declaration: data Salutation = [Either Char Name] We think it will not scale well, too, however, it is elegant due to its simplicity. Bye and thx, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: GHC and Kinds
Hello, It means that Kinds are represented by Types. Admittedly, Kinds only use a small fragment of what Types can represent, namely Arrow, and type constructor applications. So * is represented by a TyConApp with a TyCon that is called typeCon. The really annoying thing about Kinds is that there's occasionally a bit of sub-kinding. In particular error :: forall a. String - a We want to allow error foo :: Int# I have subkinding in my calculus as well, but in a completely different context. For instance, the kind of Either is + - + - * because Either is covariant in its arguments. But the kind of Either is also x - x - * (x=invariance). So we have + - + - * as the most specific kind of Either. Note, that the kind arrow in my system is contravariant as well. I think, that is a nice analogy to the type system. For example, let tau_1:(x - *) - *, tau_2:(+ - *) - *. Then tau_1 is usable whenever tau_2 is in operation. So from (+ - *) : (x - *) it follows in my system, that (x - *) - * : (+ - *) - *. Unfortunately I have to decide two contexts of the kind arrow. To understand this, consider my definition of kinds: Def.: Kinds are inductively defined as follows: * is a kind if kappa1 and kappa2 are kinds, then kappa1 - kappa2 is a kind if kappa is a kind, then + - kappa, - - kappa, x - kappa and alpha - kappa alpha is a so-called kind variable, that can be instantiated by +, - or x (not by arbitrary kinds!). Further on, we have the convention, that * - kappa has to be seen as x - kappa. What do we mean by the term kind variable? A type tau may have the kind (alpha-beta-*)-alpha-beta-*. If one applies this type, e.g., to the arrow type constructor one gaines (tau (-)): - - + - *. So information about variances is propagated. This allows for subtyping in a convenient manner. so the kind of 'a' can't be *, nor # (the kind of unboxed types). It's an open kind, written ?; both * and # are sub-kinds of ?. I have read about this issue in the sources of the GHC. I try to understand... You should nevertheless be able to encode your kind system in the same way as GHC does. This is a pity, because my kind system allows for a really nice type inference algorithm, that can deal with higher-kinded types properly. I hope, that I can transfer it to the GHC. I will write a short section for the commentary as soon as I completely understand the GHC kind system. But I have been thinking that it's over-kill to use Types for Kinds, and leads to no real saving. I think so, too, because the system from Typing Haskell in Haskell is very easy to understand and extend. Another advantage is, that it is closer to the Haskell report. I may well split the two types in the future. This would be great. Thank you for the informations, Steffen Mazanek ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: GHC and Kinds
Hello, It means that Kinds are represented by Types. Admittedly, Kinds only use a small fragment of what Types can represent, namely Arrow, and type constructor applications. So * is represented by a TyConApp with a TyCon that is called typeCon. The really annoying thing about Kinds is that there's occasionally a bit of sub-kinding. In particular error :: forall a. String - a We want to allow error foo :: Int# I have subkinding in my calculus as well, but in a completely different context. For instance, the kind of Either is + - + - * because Either is covariant in its arguments. But the kind of Either is also x - x - * (x=invariance). So we have + - + - * as the most specific kind of Either. Note, that the kind arrow in my system is contravariant as well. I think, that is a nice analogy to the type system. For example, let tau_1:(x - *) - *, tau_2:(+ - *) - *. Then tau_1 is usable whenever tau_2 is in operation. So from (+ - *) : (x - *) it follows in my system, that (x - *) - * : (+ - *) - *. Unfortunately I have to decide two contexts of the kind arrow. To understand this, consider my definition of kinds: Def.: Kinds are inductively defined as follows: * is a kind if kappa1 and kappa2 are kinds, then kappa1 - kappa2 is a kind if kappa is a kind, then + - kappa, - - kappa, x - kappa and alpha - kappa alpha is a so-called kind variable, that can be instantiated by +, - or x (not by arbitrary kinds!). Further on, we have the convention, that * - kappa has to be seen as x - kappa. What do we mean by the term kind variable? A type tau may have the kind (alpha-beta-*)-alpha-beta-*. If one applies this type, e.g., to the arrow type constructor one gaines (tau (-)): - - + - *. So information about variances is propagated. This allows for subtyping in a convenient manner. so the kind of 'a' can't be *, nor # (the kind of unboxed types). It's an open kind, written ?; both * and # are sub-kinds of ?. I have read about this issue in the sources of the GHC. I try to understand... You should nevertheless be able to encode your kind system in the same way as GHC does. This is a pity, because my kind system allows for a really nice type inference algorithm, that can deal with higher-kinded types properly. I hope, that I can transfer it to the GHC. I will write a short section for the commentary as soon as I completely understand the GHC kind system. But I have been thinking that it's over-kill to use Types for Kinds, and leads to no real saving. I think so, too, because the system from Typing Haskell in Haskell is very easy to understand and extend. Another advantage is, that it is closer to the Haskell report. I may well split the two types in the future. This would be great. Thank you for the informations, Steffen Mazanek ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
GHC and Kinds
Hello again, I have browsed the GHC commentary and I could not find a lot of information about kinds. But kinds are very important for my implementation! The parser seems to call liftedTypeKind from TypeRep. But in TypeRep we have type Kind = Type What does this mean? I briefly explain the basics of my algorithm, so that you see how much it depends on the notion of Kinds. I have the following declaration: data Kind = KVar Kindvar --kind variables | KVarInv Kindvar --inversion of kind variables | Star --corresponds to * | Cov --corresponds to + | Contr --corresponds to - | Inv --corresponds to x | Kind :- Kind --function kind deriving Eq The new atomic kinds Cov, Contr and Inv can be explained by some examples. In my system, the list type constructor, that is covariant in its argument, i.e., ([] a)([] b) whenever ab, is represented by (Tycon [] (Cov:-Star)). In contrast, the arrow type constructor's kind is given by (Contr:-(Cov:-Star)) due to its contravariance. If one tries to establish a subtype relationship, kinds are taken into consideration. How can I gently integrate this behavior in the GHC? Till now I have worked with Typing Haskell in Haskell and I really expected a declaration like data Kind = Star | Kfun Kind Kind Any help is greatly appreciated. Regards, Steffen Mazanek ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
command line option --show-iface
Hello,
the following error is slightly confusing:
ghc --show-iface
ghc-6.0.1: unrecognised flag: --show-iface
Usage: For basic information, try the `--help' option.
ghc --show-iface Unify.hi
__interface Main Unify 1 where
__export Unify Unifiable{mgu} match mguType varBind;
...
A hint in the right direction would be more
convenient :-)
Maybe in /ghc/compiler/main/DriverUtil.hs a function
unknownFlagErrUsage :: String-String - a
unknownFlagErrUsage f specusage = throwDyn
(UsageError (unrecognised flag: ++ f ++ \n ++
hint: ++ specusage))
and changing processOneArg from DriverFlags.hs
HasArg fio -
if rest /=
then fio rest return args
else case args of
[] - unknownFlagErrUsage dash_arg argument for flag expected
(arg1:args1) - fio arg1 return args1
Would this be ok?
Regards,
Steffen
___
Glasgow-haskell-users mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: literate comments
Hello, I have thought again about the relationship of Haskell and XML. Finally I come up with the following idea. Why not introduce a Haskell DTD? Not to gain better literate programming facilities, but to represent _real_ Haskell code in XML. Of course, no person would like to program Haskell in XML, but a uniform representation has its advantages nevertheless (cf. openmath [1]): * approved tools for further processing * separation of the presentation layer, pretty printing * interoperability * cross-linking (e.g., generating library summaries or in the manner of funnelweb [2], but xml-style) * objects are often serializable as xml, too The following questions are still open for me: * would the literate programming facilities really be improved? for now, Haskell plays nice with LaTeX, but not at all with XML * possible advantages of xml schema? What do you think about this? Do you see even more advantages of this approach or would it be senseless work? Regards, Steffen Mazanek [1] http://www.openmath.org/ [2] http://www.ross.net/funnelweb/ ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: GHC Lexer
Hello, LexCore is the lexer for ExternalCore. http://www.haskell.org/ghc/docs/papers/core.ps.gz For your purposes, you can ignore it. thank you for this information. I have checked out the latest cvs tree and thereby I have noticed, that Lex.lhs is now replaced by an alex file. GHC is changing so fast... Regards, Steffen Mazanek ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
GHC Lexer
Hello, to add a new keyword, say struct to the GHC, I have added ITstruct to data type Token in module Lex.lhs. Further on I have adapted ghcExtensionKeywordsFM. Is this already sufficient for lexing? In LexCore there is a function lexKeyword without a comment. It is called by lexer if the first character is %. What does this mean? Thank you, Steffen ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
literate comments
Hello, in the Haskell report the latex code environment is mentioned: http://www.haskell.org/onlinereport/literate.html Would it make sense, to add a xml like code environment as well, e.g., code.../code? Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: constructor name clashes
Hello.
Also, when declaring named fields of a type, such as
data Data1 = Data1{ok1::Bool}
data Data2 = Data2{ok2::Bool}
the field names for different type also have to be unique.
All function declarations in a module have to be unique. And, e.g., the
data constructor Data1 is a function with type Bool-Data1 and as such
it has to be globally unique as well.
Isn't that annoying? Keeping all the names unique is no easy task in my
opinion. Wouldn't it be nice if we can have something similar to structure
fields in C? Or maybe this is already present and I'm just being ignorant?
You may have a look at TREX or OHaskell. In TREX (available with Hugs)
and OHaskell
(http://www.math.chalmers.se/~nordland/ohaskell/) you can define records.
For instance, this is a valid OHaskell program:
data Monochrome = Black | White
data Color Monochrome = Red | Blue
Thereby the data type Color inherits the constructors Black and White
from Monochrome.
Even so, it is not possible to use the same constructors without
establishing a subtype relationship.
AFAIK Haskell98 lacks this possibility. But you can use named fields in
the same declaration
as long as their type remains the same.
Ciao,
Steffen
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Real world example needed for ...
Hello, I am looking for a real world example of a type constructor, that expects another type constructor as an argument in the context of subtyping, e.g., one could define --not Haskell98 data T a b c = F (a b c) a::T (-) Pt Pt a = F id b::T (-) CPt CPt b = F id l = [a,b] Thereby CPt is assumed to be a subtype of Pt. From my expectations l should be typable [T (-) CPt Pt], because of contravariance of (-). Using c::T (Either) Pt Pt and d::T (Either) CPt CPt one would gain [c,d]::T (Either) Pt Pt. I need this real world example for the sake of motivation, that variance can be expressed by Haskell kinds, e.g., in a kind system the kind of T could be (a-b-*)-a-b-*. Thereby the kind variables a and b can be instantiated by special kinds + and -, that represent co- and contravariance, respectively. So one would have T (-)::- - + - * and T (Either)::+ - + - * and so on... Any ideas are very appreciated. Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: proving the monad laws
Hello, thank you for the idea of using variables directly to see what happens. This is really a simplification for the proof. At first I thought that there should be a simpler solution and I tried to modify your approach, so that it applies to = as well, but now I am convinced :-) I have downloaded the paper of Filinski Representing Monads to take a look at the definition directly. It seems to be interesting for me, but deterringly difficult as well :-( Would it be possible to write a piece of Haskell code which checks the monadic laws automatically by simulating evaluation in this way? Maybe a little theoretical section in the monad tutorial which deals with this stuff would be a help as well. Iavor, I am really happy, that this monad is working :-) Never touch a running system or try to make it more difficult as it is! These monad transformers are still a red rag to me. Nevertheless thank you. Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Problem with Infinite Lists
Hello, all_fib :: [Float] You define all_fib to return a list of Float, but even does only work for numbers whose type is an instance of the class Integral, e.g. Int. HTH and ciao, Steffen ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Haskell for non-Haskell's sake
Hello, I am a student from Germany and I have used Haskell for several purposes as well: - to implement and compare algorithms quickly, e.g. Travelling Salesman, Sorting, etc. - to calculate state spaces and blocking probabilities in networks - to solve some of our cryptography and computability excersises :-) - to solve several programs of the online judge, although Haskell is currently not supported Further on I have written an interpreter for RATH (exploring finite relation algebras using tools written in Haskell) and in this time I use Haskell in my diplome thesis (but unfortunately for the sake of Haskell :-p). Some time ago, we had some problems with our news server and installed a new inn. This new inn was totally incompatible with the old one (or we were to clumsy to figure it out) and so the old articles seem to be lost. So it was our task to write a script, which should transform the backuped, old articles on the server into expect-scripts. I did this in Haskell and it worked satisfactorily :-) I call it the News-Reposter *g*. Haskell is my programming language of choice. It is possible, to solve problems quickly and the algorithms look so beautiful. I miss convenient and standardized libraries for gui-programming! I think, this is a serious problem. Bye, Steffen Mazanek P.S. I do my best to motivate other people to give Haskell a try, e.g. during a lecture about document-description-languages I had provided a funny example, how useful HaXml is :-) The program reads a xml-file with descriptions (age, iq, bust size *g*, all values are only estimated) of some famous women (Britney, Madonna, etc.) and puts out a nicely-formatted html-file with a final evaluation (value=iq*bustsize-100*|age-22| *g*). In case, that a woman is reading this list: One could easily invent a formula as well, which evaluates men. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Haskell-report, chapter 3 - Expressions
Thank you. The '10' should be explained in the report as well. Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
proving the monad laws
Hello, consider the following monad (which is a slight adaptation of the one used in Typing Haskell in Haskell) as given: data Error a = Error String | Ok a data TI a = TI (Subst - Int - Error (Subst, Int, a)) instance Monad TI where return x = TI (\s n - Ok (s,n,x)) TI f = g = TI (\s n - case f s n of Ok (s',m,x) - let TI gx = g x in gx s' m Error s-Error s) fail s = TI (\_ _-Error s) Now I would like to verify the monad laws. It is really easy to show that return is both a left- and a right-unit. But I got stuck with associativity: m@(TI mf) = (\a-f a = h) = = TI (\s n - case mf s n of Ok (s',m,x) - let TI gx = (\a-f a = h) x in gx s' m Error s-Error s) = ... = ((TI mf) = f) = h Is there someone outside who is willing to tell what fills the gap? A hint may be sufficient already. Or is there a tool, which finds such derivations? I have read the tutorial All about Monads, but there only is mentioned, that there is an obligation for the programmer to prove these laws. It would be helpful as well, to provide an example! I was wondering, if it is possible to simplify: let TI gx = f x =h in But the a may occur in h? Thank you. Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Exhaustive Pattern-Matching
Thank you all for your help. I will try this ghc-flag. It is interesting as well, that in contrast to Haskell Standard ML ensures, that pattern-matches are exhaustive and irredundant. Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Haskell-report, chapter 3 - Expressions
Hello,
I do not completely understand the first part of chapter 3 of the
Haskell-report.
Concretely I am stumbling about the notation of nonterminals indexed by
their precedence
level. This should be a number ranging from 0 to 9. But what about this
exp^{10}
production rule?
I would be very appreciated if someone could explain this part in some
more detail.
I am trying to introduce a new language construct into this grammar and
I want to
insert it at the right place :-)
Ciao,
Steffen
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Exhaustive Pattern-Matching
Hello, I have a question about pattern-matching. In the Haskell-report it is not postulated, that pattern matching has to be exhaustive. Would it be possible at all to implement an algorithm, which checks Haskell-style patterns for exhaustiveness? What kinds of complication can be expected? Maybe you have some pointers to other resources about this topic. Thank you, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
hiddencode
Hello,
I am using literate programming with \begin{code}...\end{code}.
But there is one problem. I want to hide some code of a module
in my documentation. Therefore another environment, e.g.
called hiddencode, would be very useful. To make things more
general: Is there the possiblity to add other code environments?
If not I would prefer a command line option.
What do you think about this?
Ciao,
Steffen
--
Steffen Mazanek - www.steffen-mazanek.de - GPG: 791F DCB3
Haskell, that's where I just curry until fail, unwords
any error, drop all undefined, maybe break, otherwise
in sequence span isControl and take max $, id: (d:[])
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: hiddencode
What about:
\long\def\ignore#1{}
and then
\ignore{
\begin{code}
main = putStrLn I am not in the docs!
\end{code}
} %ignore
That is fine! Thank you.
Nevertheless, additional environments would be
useful, too, e.g. if you would like to have different
font sizes in your documentation.
Ciao,
Steffen
--
Steffen Mazanek - www.steffen-mazanek.de - GPG: 791F DCB3
Haskell, that's where I just curry until fail, unwords
any error, drop all undefined, maybe break, otherwise
in sequence span isControl and take max $, id: (d:[])
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: labelled fields
Ok, I had missed something: I can write instead: data Type = TCon String (Maybe String) ... and declare a function lmtc lmtc (TCon _ x) = x ... But why not allow syntactic sugar? Sorry, Steffen -- Steffen Mazanek - www.steffen-mazanek.de - GPG: 791F DCB3 Haskell, that's where I just curry until fail, unwords any error, drop all undefined, maybe break, otherwise in sequence span isControl and take max $, id: (d:[]) ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: AW: simulating dynamic dispatch
Interestingly, when I want hugs to show me the type of fun::(forall a.[a]-Int)-[b]-[c]-Int it tells me: ERROR - Use of fun requires at least 1 argument Why that? At least I have explicitely specified the type. Hmm, ghci behaves properly. But using hugs I get the same error :-(. No idea! Maybe some additional flags have to be set? Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
History of Haskell, first draft
Hello, a first draft of my little Haskell-history collection is online now: http://pseiko.gmxhome.de/pseiko/Haskell-History.html Please note, that one part is still just copied from http://www.idt.mdh.se/kurser/cd5100/ht02/history.html but I hope it will evolve quickly. Moreover some parts are still missing. So please understand it as a framework and base where all kinds of additional contributions are pluggable. A big thank you to all helpers. Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
old hugs versions?
Hello, are there any valid links in the whole internet pointing to old versions of hugs? Concretely I need hugs-1.3b and all hints how to find it would be very appreciated. One may ask what the hell I want to do with this old stuff :-). My intention is to compare its parser.y file with the one of Johan Nordlanders ohugs (http://www.cs.chalmers.se/~nordland/ohugs/). Thanks in advance, Steffen Mazanek ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Haskell History
Hello, I want to create a source of historic information to delight the Haskell community and therefore I need a lot of material relating the following topics: - from lambda calculus to functional programming - other roots of Haskell (e.g. Gofer, ...) - genesis of the well known and beloved standard Haskell98 This website should act as an archive of old releases of popular Haskell interpreters and compilers, too (seemingly there is nothing online at present). Sometimes you need an old release of a particular software, e.g. for comparisons and you become really bored with following quit a lot of dead links in the internet, wasting time and staying without results. Help me to close this existing gap. All suggestions are welcome. Steffen Mazanek ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Haskell History
Hello again, See Conception, evolution, and application of functional programming languages by Paul Hudak. That's a great starting point for a History of Haskell page: http://portal.acm.org/citation.cfm?doid=72551.72554 thank you, I will read it. You're welcome to steal the simple layout of the Learning Haskell page and maybe someone will make you a logo... Great idea, thank you again. I am not a graphic-freak. Maybe someone else can realize my plan :-). I have a historic world map in mind, which becomes flooded by little lambdas *g*. I hope to present a first draft of this website in the nearer future. Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Function wows
Hello, frombin :: [Bit] - Int frombin [] = 0 frombin (n:ns) = sum (n:( frombin (map (*2) ns))) frombin takes a list of Bits and returns an Int, but (:) needs a list as its second argument. Try something like frombin (n:ns) = n + 2*(frombin ns) or frombin = foldr (\x y-x+2*y) 0 Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Tutorial for literate Haskell
Hi,
When I ran into the same question some time ago I tried that,
but found that the \verbatim was interpreted to0 literally, so
that the \end{code} does not terminate it. Could you give a
complete short example that works for you?
My own solution was to copy the definition of verbatim from the
base files, and define code the same way in a separate style file.
Hmm, there were no problems in simply doing so.
MainFile.tex:
\documentclass[12pt,oneside]{report}
\usepackage[latin1]{inputenc}
\usepackage{verbatim}
\begin{document}
\newenvironment{code}{\footnotesize\verbatim}{\endverbatim\normalsize}
\begin{titlepage}
...
\begin{document}
...
\input{HaskellModule.lhs}
...
HaskellModule.lhs:
\chapter{The Module Foo}
\label{Foo}
Maybe some text...
We call our module Foo, because this name is very
meaningful.
\begin{code}
module Foo where
\end{code}
and so on
Thats it.
I hope this will help.
Ciao,
Steffen
--
Steffen Mazanek
Werner Heisenberg Weg 102 App. 232
85579 Neubiberg
GPG key fingerprint: A165 227D B288 5E10 701D BF5F E91C 6B88 24C8 397D
http://blackhole.pca.dfn.de:11371/pks/lookup?op=getsearch=0x24C8397D
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: looking for Database Interface in Haskell
Have a look here: http://haskell.cs.yale.edu/haskellDB/ ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Tutorial for literate Haskell
Hello.
I do Literate Programming this way:
At first I define a Latex environment code as verbatim
e.g. so: \newenvironment{code}{\footnotesize\verbatim}{\endverbatim\normalsize}
This environment is understood by the Haskell compilers.
All my modules are own documents concluded in the main tex-file with
\input{...}.
Alternatively I sometimes use lambdaTeX which typesets the code
really nice (problem: latex2html doesn't understand it).
Hope that will help.
Ciao,
Steffen
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Anyone calculating Nash or Wardrop equilibria in Haskell?
Hello. Haskells declarativity is really useful to transform mathematical models into data types and algorithms. In the context of a seminary I have dealt with equilibria concepts (especially Nash and Wardrop equilibrium) in loss networks. (based on Non-cooperative routing in loss networks by Altman et al.) Thereby I have noticed that some algorithms are very easy to implement in Haskell, e.g. the state space or the blocking probability. Surely these algorithms are not efficient, they should just do their jobs. On the other hand there are algorithms, too, which appear to be really hard and long winded to implement, e.g. the equilibria by itself. My question: Is there an elegant way of programming a numerical solver of problems like given the conditions ... find a solution which minimizes/maximizes the following function Presumably there is no such way in general, but maybe someone can give a hint, how to tackle these kinds of problems. Or maybe there are some libraries doing this job. Thanks in advance and best greetings. Steffen Mazanek ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Regular expressions as Haskell Type Generators?
Hello, I am wondering if it would be worth while (and possible) to allow the definition of types by regular expressions, e.g. data Date = Date #RegExp([0-9][0-9]-[0-9][0-9]-[0-9][0-9][0-9][0-9]) or easier with some auxiliary constructs. Clearly there would be some drawbacks with the use of standard String-operations or type checking. But in praxi it may be absolutely relevant. Or is some work already done in this direction? Ciao, Steffen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
O'Haskell
Hello. I am toying with the idea of implementing the OHaskell-concepts of Johan Nordlander in the GHC (as a diploma thesis). Simon Marlow adviced me to do some market research in this group and here we go. I am interested in all kinds of comments, advices, scrupulosites... Thanks and greetings, Steffen ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: O'Haskell
Oh, sorry. I was asked for the link: http://www.math.chalmers.se/~nordland/ohaskell/ Nice greetings, Steffen ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
