Re: [GHC] #3909: Priority queues in containers
#3909: Priority queues in containers ---+ Reporter: LouisWasserman |Owner: LouisWasserman Type: feature request | Status: assigned Priority: normal |Milestone: Component: libraries (other) | Version: 6.12.1 Keywords: containers, priority queue | Difficulty: Os: Unknown/Multiple| Testcase: Architecture: Unknown/Multiple| Failure: None/Unknown ---+ Comment(by milan): Replying to [comment:20 LouisWasserman]: Even lazy pairing heaps have the O(n) worst-case delete-min performance. Amortization isn't going to cut it. Have you looked at the implementation? Let me aside, even Okasaki conjectures that I inserts M merges and D delete-mins takes O(I+D log N) in the persistent setting (proof by authority:) The trik is the following -- lazy pairing heaps use back-to-front variant (both pairings and final merge is performed from back to front). When there are three children of the root, you merge the newest two and merges the result to the oldest child, immediately, but lazily. So if you do a sequence of inserts followed by a delete-min, all previous versions of the heap are affected -- performing a delete-min now in any version (except the latest) will take O(1). As I said, there is not a solid proof, but neither could anyone find a sequence of operations in persistent setting that would break claimed bound. Wikipedia suggested that skew heaps usually outperformed leftist heaps. I wrote a reasonably refined implementation of skew heaps and got Times (ms) minmean+/-sd medianmax Pairing:8.000 12.401 4.274 12.001 28.002 Binomial: 24.001 31.842 6.200 28.002 44.003 Skew: 24.001 31.922 6.280 32.002 48.003 for sorting of random data. Also, more importantly, skew heaps don't even support amortized O(1) insertion, let alone worst-case. Binomial heaps support amortized O(1) insertion, worst-case O(log n). There's a variant of binomial heaps which supports worst-case O(log n) insertion, but it's not very pretty to code, and it would make an already large amount of code blow up hugely. I'm willing to settle for the amortized bounds there. Conclusion: I'm inclined to stick with binomial heaps. Further experimentation has indicated that there isn't much difference between lazy and strict sorting speeds, so I'm inclined to stick with the strict implementation -- again for the crowd who needs real-time performance. I would probably stick with lazy pairing heaps, and if the time bounds would discovered to be wrong, to switch it with binomial implementation. The only issue of lazy pairing heaps is amortization (let the conjecture aside). I personally think the performance win justifies this. Of course, providing a real-time impementation, preferably with the same API, is a great idea. Maybe in another package? And a last think -- do you think {{{ViewQ}}} is a good idea? I would prefer {{{extract}}} to return {{{Maybe (a, PQueue a)}}}. I agree it is not so elegant in pattern matching, but * if the module is qualified, you have to write {{{PQueue.(:^) a queue}}} with the new-style qualified operator, which is horrible * you cannot use monadic combinators. If the extract returns in the {{{Maybe}}} monad, you can. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3909#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3737: inlining happens on foldl1 and does not happen on direct application of combinator
#3737: inlining happens on foldl1 and does not happen on direct application of combinator -+-- Reporter: guest |Owner: Type: bug | Status: new Priority: normal|Milestone: 6.14.1 Component: Compiler | Version: 6.10.4 Keywords:| Difficulty: Os: Linux | Testcase: Architecture: x86 | Failure: Runtime performance bug -+-- Comment(by simonpj): I hope this may be fixed by the same fix as #3736. Could you try? Simon -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3737#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3736: GHC specialising instead of inlining
#3736: GHC specialising instead of inlining -+-- Reporter: guest |Owner: Type: bug | Status: new Priority: normal|Milestone: 6.14.1 Component: Compiler | Version: 6.10.4 Keywords:| Difficulty: Os: Linux | Testcase: Architecture: x86 | Failure: Runtime performance bug -+-- Comment(by simonpj): Great stuff. Thank you for cutting down the test case Ian. That made it easy to find the bug. And it was easy to fix too: {{{ Fri Mar 5 17:27:59 GMT 2010 simo...@microsoft.com * Fix Trac #3736: do not preInlineUnconditionally with INLINE preInlineUnconditionally was, in effect, nuking an INLINE pragma, with very bad effect on runtime in this program. Fortunately the fix is very simple. See Note [InlineRule and preInlineUnconditionally] in SimplUtils. M ./compiler/simplCore/SimplUtils.lhs +24 }}} * Can you see if it is indeed fixed, and if so close this ticket? * I believe this may in fact fix #3737 as well. Can one of you try? * I'm not sure it's worth making a test case, but Ian's `Main.hs` is small enough to try. Ian, I'm not sure how to make a regression test that says does ./main 1 run faster than ./main 2 or whatever. If you think it's worth it, pls add one. Do not merge to 6.12; it's all 6.14 code. Simon -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3736#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1954: Incorrect Defined but not used warning when using GeneralizedNewtypeDeriving
#1954: Incorrect Defined but not used warning when using GeneralizedNewtypeDeriving -+-- Reporter: magnus|Owner: igloo Type: merge | Status: new Priority: normal|Milestone: 6.12 branch Component: Compiler | Version: 6.8.1 Keywords:| Difficulty: Unknown Os: Unknown/Multiple | Testcase: rename/should_compile/T1954 Architecture: Unknown/Multiple | Failure: None/Unknown -+-- Changes (by simonpj): * owner: = igloo * testcase: = rename/should_compile/T1954 * type: bug = merge Comment: Thanks for the reminder. It was pretty easy to fix {{{ Tue Mar 9 09:35:55 PST 2010 simo...@microsoft.com * Fix Trac #1954: newtype deriving caused 'defined but not used' error We were getting a bogus claim that a newtype data constructor was unused. The fix is easy, although I had to add a field to the constructor TcEnv.NewTypeDerived See Note [Newtype deriving and unused constructors] in TcDeriv M ./compiler/typecheck/TcDeriv.lhs -3 +25 M ./compiler/typecheck/TcEnv.lhs -8 +15 M ./compiler/typecheck/TcInstDcls.lhs -1 +1 }}} Could be merged to 6.12, but not if it causes any trouble. Simon -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/1954#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3909: Priority queues in containers
#3909: Priority queues in containers ---+ Reporter: LouisWasserman |Owner: LouisWasserman Type: feature request | Status: assigned Priority: normal |Milestone: Component: libraries (other) | Version: 6.12.1 Keywords: containers, priority queue | Difficulty: Os: Unknown/Multiple| Testcase: Architecture: Unknown/Multiple| Failure: None/Unknown ---+ Comment(by LouisWasserman): Aha! This wasn't how I'd imagined that lazy pairing heaps worked, but I love it. Yeah, that's beautiful, let me change my own implementation... **works** ViewQ is...tricky. I included it by analogy to Data.Sequence, which has the same issue. I'm...not entirely sure what the best policy is. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3909#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3909: Priority queues in containers
#3909: Priority queues in containers ---+ Reporter: LouisWasserman |Owner: LouisWasserman Type: feature request | Status: assigned Priority: normal |Milestone: Component: libraries (other) | Version: 6.12.1 Keywords: containers, priority queue | Difficulty: Os: Unknown/Multiple| Testcase: Architecture: Unknown/Multiple| Failure: None/Unknown ---+ Comment(by milan): Replying to [comment:22 LouisWasserman]: Aha! This wasn't how I'd imagined that lazy pairing heaps worked, but I love it. Yeah, that's beautiful, let me change my own implementation... **works** Sorry, I mentioned it only in comment 17, not in the benchmark description :( ViewQ is...tricky. I included it by analogy to Data.Sequence, which has the same issue. I'm...not entirely sure what the best policy is. I understand the idea, but personally I am strongly for {{{Maybe (a, PQueue a)}}}, if there is a poll :) -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3909#comment:23 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3909: Priority queues in containers
#3909: Priority queues in containers ---+ Reporter: LouisWasserman |Owner: LouisWasserman Type: feature request | Status: assigned Priority: normal |Milestone: Component: libraries (other) | Version: 6.12.1 Keywords: containers, priority queue | Difficulty: Os: Unknown/Multiple| Testcase: Architecture: Unknown/Multiple| Failure: None/Unknown ---+ Comment(by LouisWasserman): Hmmmkay. I'm going to make my own vote for {{{Maybe (a, PQueue a)}}}, and change it, since we appear to be in charge... After doing my own experiments with lazy pairing heaps, I'm still not sure I'm willing to support lazy pairing heaps, again out of concern for the real-time-performance crowd. The distinction is really the following: Binomial queues support amortized O(1) insertion, but worst-case O(log n). Pairing heaps support amortized O(log n) delete-min, but worst-case O(n). Okasaki doesn't debate worst-case performance. I'm convinced that this approach doesn't risk O(n^2) performance in a persistent context, now, which is a significant improvement, but I'm not fully convinced it's enough yet. Uploading my updated versions now. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3909#comment:24 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3909: Priority queues in containers
#3909: Priority queues in containers ---+ Reporter: LouisWasserman |Owner: LouisWasserman Type: feature request | Status: assigned Priority: normal |Milestone: Component: libraries (other) | Version: 6.12.1 Keywords: containers, priority queue | Difficulty: Os: Unknown/Multiple| Testcase: Architecture: Unknown/Multiple| Failure: None/Unknown ---+ Comment(by LouisWasserman): Another minor concern: I'm not sure lazy pairing heaps can support linear-time unordered traversals, or anything of the sort. I still need to think about that, because it's not impossible that the same operations actually do take linear time still... -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3909#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3909: Priority queues in containers
#3909: Priority queues in containers ---+ Reporter: LouisWasserman |Owner: LouisWasserman Type: feature request | Status: assigned Priority: normal |Milestone: Component: libraries (other) | Version: 6.12.1 Keywords: containers, priority queue | Difficulty: Os: Unknown/Multiple| Testcase: Architecture: Unknown/Multiple| Failure: None/Unknown ---+ Comment(by milan): Replying to [comment:24 LouisWasserman]: Hmmmkay. I'm going to make my own vote for {{{Maybe (a, PQueue a)}}}, and change it, since we appear to be in charge... Great :) After doing my own experiments with lazy pairing heaps, I'm still not sure I'm willing to support lazy pairing heaps, again out of concern for the real-time-performance crowd. The distinction is really the following: Binomial queues support amortized O(1) insertion, but worst-case O(log n). Pairing heaps support amortized O(log n) delete-min, but worst-case O(n). Okasaki doesn't debate worst-case performance. The lazy pairing heaps are really only amortized -- you know (if the conjecture is right) that I inserts, M merges and D delete-mins take O(I + D log N), but a delete-min can take up to O(N) time (which cannot happen frequently, of course). If we want structure with worst-case bounds, it is not (any kind of) pairing heaps. For me, a quicker structure with amortized bounds is better in Haskell. If you for example perform a heap-sort, than the amortized bounds works well and you have O(N log N) guaranteed complexity. Only thing that doesn't work is now immediately perform this delete-min in O(log N). But this kind of operations are not common in Haskell -- you would have to carefully evaluate every operation, because trivially performing 'insert' would probably create only a thunk which the first delete-min would have to evaluate and thus could take O(N). But, as you said, binomial heaps are worst-case. They have provable bounds. And are a common knowledge -- which this variant of lazy pairing heap is not. How is it with stability -- don't you know? Milan -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3909#comment:26 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3909: Priority queues in containers
#3909: Priority queues in containers ---+ Reporter: LouisWasserman |Owner: LouisWasserman Type: feature request | Status: assigned Priority: normal |Milestone: Component: libraries (other) | Version: 6.12.1 Keywords: containers, priority queue | Difficulty: Os: Unknown/Multiple| Testcase: Architecture: Unknown/Multiple| Failure: None/Unknown ---+ Comment(by milan): Replying to [comment:25 LouisWasserman]: Another minor concern: I'm not sure lazy pairing heaps can support linear-time unordered traversals, or anything of the sort. I still need to think about that, because it's not impossible that the same operations actually do take linear time still... Well, that is a good point. Long story short, with this representation it will take O(N log N) in some cases. Maybe the representation could be changed, but not straightforwardly. So -- the binomial heaps? -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3909#comment:27 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3909: Priority queues in containers
#3909: Priority queues in containers ---+ Reporter: LouisWasserman |Owner: LouisWasserman Type: feature request | Status: assigned Priority: normal |Milestone: Component: libraries (other) | Version: 6.12.1 Keywords: containers, priority queue | Difficulty: Os: Unknown/Multiple| Testcase: Architecture: Unknown/Multiple| Failure: None/Unknown ---+ Comment(by LouisWasserman): Yeah. When I've needed real-time performance, I'd probably do something like {{{ insert x $! queue }}} which defers the lazy work by one operation, but only by one operation. Essentially, I'd like to be able to guarantee that {{{seq}}} actually guarantees a fully evaluated spine, cf. Data.Map or Data.IntMap. I'm willing, though, to perhaps co-author a package for pairing heaps, and then to recommend that package in the containers documentation as a speedy implementation for people who are willing to settle for amortized time bounds in exchange for overall speedy performance. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3909#comment:28 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1496: Newtypes and type families combine to produce inconsistent FC(X) axiom sets
#1496: Newtypes and type families combine to produce inconsistent FC(X) axiom sets +--- Reporter: sorear |Owner: simonpj Type: bug | Status: new Priority: normal |Milestone: 6.12 branch Component: Compiler (Type checker) | Version: 6.7 Keywords: | Difficulty: Unknown Os: Unknown/Multiple | Testcase: Architecture: Unknown/Multiple | Failure: None/Unknown +--- Changes (by jmaessen): * cc: jmaes...@… (added) * failure: = None/Unknown Comment: Here's a simple example program that violates the invariant of `Set` while using ''only'' newtype deriving (and not more complex extensions such as multiparameter type classes or type functions): {{{ {-# LANGUAGE GeneralizedNewtypeDeriving #-} module Main(main) where import Data.Set class IsoInt a where convFromInt :: item Int - item a instance IsoInt Int where convFromInt = id newtype Down a = Down a deriving (Eq, Show, IsoInt) instance Ord a = Ord (Down a) where compare (Down a) (Down b) = compare b a asSetDown :: Set (Down Int) - Set (Down Int) asSetDown = id a1 = toAscList . asSetDown . convFromInt . fromAscList $ [0..10] a2 = toAscList . asSetDown . fromAscList . reverse . convFromInt $ [0..10] main = do print a1 print a2 }}} -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/1496#comment:26 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3909: Priority queues in containers
#3909: Priority queues in containers ---+ Reporter: LouisWasserman |Owner: LouisWasserman Type: feature request | Status: assigned Priority: normal |Milestone: Component: libraries (other) | Version: 6.12.1 Keywords: containers, priority queue | Difficulty: Os: Unknown/Multiple| Testcase: Architecture: Unknown/Multiple| Failure: None/Unknown ---+ Comment(by milan): Replying to [comment:28 LouisWasserman]: Yeah. When I've needed real-time performance, I'd probably do something like {{{ insert x $! queue }}} which defers the lazy work by one operation, but only by one operation. Essentially, I'd like to be able to guarantee that {{{seq}}} actually guarantees a fully evaluated spine, cf. Data.Map or Data.IntMap. I'm willing, though, to perhaps co-author a package for pairing heaps, and then to recommend that package in the containers documentation as a speedy implementation for people who are willing to settle for amortized time bounds in exchange for overall speedy performance. Tomorrow I am going to implement leftist-heaps, just for comparison with binomial heaps. If you don't mind, I would wait a bit with the pairing heaps, I want to try to prove the complexity of the lazy variant. Maybe something will come out of it (perhaps a different representation that would address the traverse in linear time issue). -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3909#comment:29 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #3909: Priority queues in containers
#3909: Priority queues in containers ---+ Reporter: LouisWasserman |Owner: LouisWasserman Type: feature request | Status: assigned Priority: normal |Milestone: Component: libraries (other) | Version: 6.12.1 Keywords: containers, priority queue | Difficulty: Os: Unknown/Multiple| Testcase: Architecture: Unknown/Multiple| Failure: None/Unknown ---+ Comment(by LouisWasserman): Sounds good. I'm uploading a quickie implementation of skew heaps, which Wikipedia says should beat leftist heaps, but which is beaten by my binomial heaps. I'd be interested to help with the proof that lazy pairing heaps are amortized O(log n), and I certainly believe the claim, but I'm still inclined to use binomial heaps in containers, and then the two of us should co-release a lazy pairing heap implementation that we recommend in the containers documentation. Look forward to seeing your results. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/3909#comment:30 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #915: Implement list fusion using streams instead of foldr/build
#915: Implement list fusion using streams instead of foldr/build -+-- Reporter: simonpj |Owner: Type: task | Status: new Priority: normal|Milestone: 6.12 branch Component: libraries/base| Version: 6.8 Keywords: fusion| Difficulty: Project (more than a week) Os: Unknown/Multiple | Testcase: N/A Architecture: Unknown/Multiple | Failure: None/Unknown -+-- Changes (by LouisWasserman): * cc: wasserman.lo...@… (added) -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/915#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1434: Slow conversion from Double to Int
#1434: Slow conversion from Double to Int --+- Reporter: g...@… |Owner: Type: task | Status: new Priority: normal |Milestone: 6.12 branch Component: libraries/base | Version: 6.4.1 Keywords: rules | Difficulty: Unknown Os: Unknown/Multiple | Testcase: Architecture: Unknown/Multiple | Failure: Runtime performance bug --+- Comment(by LouisWasserman): Is there anything going on here, except that we just need to add in all the rules for the various truncated types? -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/1434#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
RE: Equality constraint type mismatch
| type family T a :: * | my_id :: f a - f a; my_id = id | x :: T a - T a; x = my_id | | | IMHO, this was not clear from the documentation or from the error | message (It certainly _looks_ like T a should match f a...). | Thanks for the explanation. Did you read this? http://haskell.org/haskellwiki/GHC/Type_families#Injectivity.2C_type_inference.2C_and_ambiguity Please edit it to improve the clarity, or add a whole new sub-section if you think that would be clearer. It's a wiki. Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
nasty things possible with generalized newtype deriving
Hello guys, are you following this Haskell Cafe thread: http://www.mail-archive.com/haskell-c...@haskell.org/msg72300.html Seems that you can do ugly things with GHC’s current implementation of generalized newtype deriving. For example, you can easily construct sets with corrupted internal structure even if there are no bogus Ord instances. Best wishes, Wolfgang ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
ghc ftp site
Hi, Could someone tell me who is in charge of the ghc ftp site these days? I need to upload a bootstrap compiler to build MacPort's ghc on Snow Leopard and the permissions of the 6.10 - 6.1 directories have changed. I no longer can write there. Best Wishes, Greg ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
[Haskell] generalized newtype deriving breaks type class invariants. that is bad.
On Mon, Mar 08, 2010 at 11:32:16PM +0100, Wolfgang Jeltsch wrote: Generalized newtype deriving doesn’t just allow otherwise undefinable functions to be defined. It probably also allows for faster function implementations. For example, with the above conv method, you could probably convert a list of some type [t] into a list of type [Wrapped t] in O(1) time. If you would code this conversion by hand, it would take O(n) time, of course. So you can! wrapList :: [a] - [Wrapped a] wrapList xs = conv xs wrapList Hello [Wrap 'H',Wrap 'e',Wrap 'l',Wrap 'l',Wrap 'o'] This is quite interesting. And perhaps very, very bad. Take this example: newtype Down a = Down a deriving (Iso a, Show, Eq) instance Ord a = Ord (Down a) where compare (Down x) (Down y) = compare y x downSet :: Set.Set a - Set.Set (Down a) downSet ss = conv ss xs = abcdef sxs1 = downSet (Set.fromList xs) sxs2 = Set.fromList (map Down xs) Set.toAscList sxs1 [Down 'a',Down 'b',Down 'c',Down 'd',Down 'e',Down 'f'] Set.toAscList sxs2 [Down 'f',Down 'e',Down 'd',Down 'c',Down 'b',Down 'a'] We have been able to break the invarients of 'Set' using newtype deriving of a completely unrelated class 'Iso'. It seems that generalized newtype deriving may break type classes in a big way. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] ANN: hsndfile 0.4
i'm pleased to announce version 0.4 of hsndfile [1], a haskell interface to libsndfile [2]. in version 0.4 the buffer i/o interface has been simplified and instances for i/o based on the vector package [3] is provided by hsndfile-vector [4]. enjoy! sk [1] http://haskell.org/haskellwiki/Hsndfile [2] http://www.mega-nerd.com/libsndfile/ [3] http://hackage.haskell.org/package/vector [4] http://hackage.haskell.org/package/hsndfile-vector ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] GT-VMT 2010: cfp
Call for Participation 9th International Workshop on Graph Transformation and Visual Modeling Techniques (GT-VMT 2010) http://www.cs.le.ac.uk/events/gtvmt10/ Satellite Event of ETAPS 2010, Cyprus -- March 20-21, 2010 == * Scope * GT-VMT 2010 is the ninth workshop of a series that serves as a forum for all researchers and practitioners interested in the use of graph-based notation, techniques, and tools for the specification, modeling, validation, manipulation and verification of complex systems. The aim of the workshop is to promote engineering approaches that provide effective sound tool support for visual modeling languages, enhancing formal reasoning at the semantic level (e.g., for model analysis, transformation, and consistency management) in different domains, such as UML, Petri nets, Graph Transformation or Business Process/Workflow Models. * Workshop Program SATURDAY 20 MARCH 2010 9:00-9:15 Opening 9:15-10:30 Invited talk: Fernando Orejas: Symbolic Attributed Graphs and Attributed Graph Transformation 10:30-11:00 Break 11:00-12:30 Session on Foundations Maarten de Mol and Arend Rensink. A Graph Representation for Ordered Edges. Davide Grohmann and Marino Miculan. Graph Algebras for Bigraphs. Christoph Blume, Sander Bruggink, and Barbara K�nig. Recognizable Graph Languages for Checking Invariants. 12:30-14:00 Lunch 14:00-15:30 Session on Modeling and Modeling Environments Frank Hermann, Andrea Corradini, Hartmut Ehrig, and Barbara K�nig. Efficient Process Analysis of Transformation Systems Based on Petri nets. Berthold Hoffmann and Mark Minas. Defining Models - Meta Models versus Graph Gammars. Torsten Strobl and Mark Minas. Specifying and generating editing environments for interactive animated visual models. 15:30-16:00 Break 16:00-17:00 Session on Interactions Vojtech Rehak, Petr Slovak, Jan Strejcek, and Loic Helouet. Decidable Race Condition and Open Coregions in HMSC. Abubakar Hassan, Ian Mackie, and Shinya Sato. A light-weight abstract machine for interaction nets. 17:00-17:30 Discussion SUNDAY 21 MARCH 2010 9:30-11:00 Session on Model Transformation Eugene Syriani and Hans Vangheluwe. De-/Re-constructing Model Transformation Languages. Bernhard Schaetz. Verification of Model Transformations. Paolo Bottoni, Andrew Fish, and Francesco Parisi-Presicce. Preserving constraints in horizontal model transformations. 11:00-11:30 Break 11:30-12:30 Session on Foundations Paolo Torrini, Reiko Heckel, Istvan Rath, and Gabor Bergmann. Stochastic Graph Transformation with Regions. Wolfram Kahl. Cotabulations, Bicolimits and Van-Kampen Squares in Collagories. 12:30-14:00 Lunch * Workshop organizers Jochen Kuester, IBM Research, Switzerland Emilio Tuosto, University of Leicester, UK * Program Committee Paolo Baldan (University of Padova, Italy) Artur Boronat (University of Leicester, UK) Andrea Corradini (University of Pisa, Italy) Claudia Ermel (TU Berlin, Germany) Gregor Engels (University of Paderborn, Germany) Reiko Heckel (University of Leicester, UK) Thomas Hildebrandt (ITU, Denmark) Holger Giese (HPI Potsdam, Germany) Barbara K�nig (University of Duisburg-Essen, Germany) Jochen K�ster (IBM Research - Zurich, Germany) Alberto Lluch Lafuente (IMT Institute for Advanced Studies Lucca, Italy) Juan de Lara (Universidad Aut�noma de Madrid, Spain) Mark Minas (Universit�t der Bundeswehr M�nchen, Germany) Francesco Parisi-Presicce (University of Rome, Italy) Arend Rensink (University of Twente, Netherlands) Gabriele Taentzer (University of Marburg, Germany) Emilio Tuosto (University of Leicester, UK) D�niel Varr� (TU Budapest, Hungary) Erhard Weinell (RWTH Aachen University, Germany) Albert Z�ndorf (University of Kassel, Germany) * More information on the workshop is available through the webpage: http://www.cs.le.ac.uk/events/gtvmt10/ -- *** Emilio Tuosto Department of Computer Science University of Leicester Leicester, LE1 7RH United Kingdom Tel. +44 (0) 116 252 5392 Fax. +44 (0) 116 252 3915 homepage - http://www.cs.le.ac.uk/people/et52 *** ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Re: [Haskell-cafe] generalized newtype deriving allows the definition of otherwise undefinable functions
On Tue, Mar 09, 2010 at 09:56:45AM -0500, Jan-Willem Maessen wrote: It occurs to me to observe: if we give class constraints in data types some force, and write: data Ord a = Set a = ...[internals go here]... Would this be enough to cue us that Set has a more interesting kind than just * - * ? Yes. I was thinking something along the same lines. Could this just be another example of contravariance flipping the meaning of quantification? If we take the simpler example given: class Iso a where conv :: item a - item Int let's give the whole type class Iso a where conv :: forall (item :: * - *) . item a - item Int It seems to me the issue may not be with newtype deriving, but with that universal quantification over a type constructor. If we were to declare 'Set' like so data Ord a = Set a = ... like Jan-Willem suggests, then it seems that 'Set' should not be able to unify with 'item' since it has the extra 'Ord' consraint on the contravariant argument to item and item is universally quantified. Item would need a psuedo-type like (Ord a = item :: a - *) to match. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] ANN: gloss-1.0.0.2: Painless 2D vector graphics, animations and simulations.
Gloss hides the pain of drawing simple vector graphics behind a nice data type and a few display functions. Gloss uses OpenGL and GLUT under the hood, but you won't have to worry about any of that. Get something cool on the screen in under 10 minutes. A simple animated example is: import Graphics.Gloss main = animateInWindow My Window (200, 200) (10, 10) white $ \time - Rotate (time * 100) $ Color red $ Line [(0, 0), (100, 100)] animateInWindow first takes the name, size, position and background color of the window. The final argument is a function from the time (in seconds) from when the program started, to a picture. Once the window is open you can pan around, zoom and rotate the animation using the mouse. Pictures of more detailed examples are at: http://trac.haskell.org/gloss/ Try it out now with: cabal update cabal install gloss cabal install gloss-examples gloss-styrene then right-click drag to rotate the box.. Ben. ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Haskell course, training
Am Montag, 8. März 2010 23:17:56 schrieb Henning Thielemann: On Sun, 7 Mar 2010, G?nther Schmidt wrote: I think I've reached the point where I need some tutoring, so provided I've got money for travel and course fees, and time, where do I get it? I'm not a student so some courses aren't available to me. How about visiting our Haskell meeting in Leipzig, June 4th? By the way, has this been announced already? Is the program already fixed or are applications for a talk or a tutorial still welcome? To be more precise, would the organizers be interested in something about dependent types? I might be able to offer something in this direction. Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: more thoughts on Finally tagless
Stephen Tetley wrote: The finally tagless style is an implementation of the TypeCase pattern (Bruno C. d. S. Oliveira and Jeremy Gibbons): http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/typecase.pdf The finally tagless style is slightly more general. The TypeCase paper emphasizes that TypeCase is a pattern to define a _closed_ type-indexed function -- the indexed family is fixed but the collection of functions is extensible. This is in contrast to type classes, where the collection of functions is fixed (by the class declaration) but the indexed family is extensible (more type class instances can be defined at any time). The tagless final approach permits the definition of an extensible family of open type-indexed functions. For example, we can define a `data type' of expressions and extend it at any time with more expression forms *and* more processing functions (e.g., a new way to print or compile an expression). With the tagless final approach, we have the extensibility in both dimensions. I'll be talking about this extensibility at some length in two weeks, at the Spring School on Generic and Indexed Programming. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] generalized newtype deriving breaks type class invariants. that is bad.
On Mon, Mar 08, 2010 at 11:32:16PM +0100, Wolfgang Jeltsch wrote: Generalized newtype deriving doesn’t just allow otherwise undefinable functions to be defined. It probably also allows for faster function implementations. For example, with the above conv method, you could probably convert a list of some type [t] into a list of type [Wrapped t] in O(1) time. If you would code this conversion by hand, it would take O(n) time, of course. So you can! wrapList :: [a] - [Wrapped a] wrapList xs = conv xs wrapList Hello [Wrap 'H',Wrap 'e',Wrap 'l',Wrap 'l',Wrap 'o'] This is quite interesting. And perhaps very, very bad. Take this example: newtype Down a = Down a deriving (Iso a, Show, Eq) instance Ord a = Ord (Down a) where compare (Down x) (Down y) = compare y x downSet :: Set.Set a - Set.Set (Down a) downSet ss = conv ss xs = abcdef sxs1 = downSet (Set.fromList xs) sxs2 = Set.fromList (map Down xs) Set.toAscList sxs1 [Down 'a',Down 'b',Down 'c',Down 'd',Down 'e',Down 'f'] Set.toAscList sxs2 [Down 'f',Down 'e',Down 'd',Down 'c',Down 'b',Down 'a'] We have been able to break the invarients of 'Set' using newtype deriving of a completely unrelated class 'Iso'. It seems that generalized newtype deriving may break type classes in a big way. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generalized newtype deriving allows the definition of otherwise undefinable functions
Am Dienstag, 9. März 2010 07:24:35 schrieb Steffen Schuldenzucker: On 03/08/2010 10:45 PM, Wolfgang Jeltsch wrote: The point is, of course, that such conversions are not only possible for binary operations but for arbitrary values and that these conversions are done by a single generic function conv. I don’t think it would be possible to implement conv without generalized newtype deriving. Any thoughts? Hi Wolfgang, it's not exactly the same, but... import Control.Applicative newtype Wrapped a = Wrap a deriving Show instance Functor Wrapped where fmap f (Wrap x) = Wrap $ f x instance Applicative Wrapped where pure = Wrap (Wrap f) * (Wrap x) = Wrap $ f x convBinOp :: (a - a - a) - (Wrapped a - Wrapped a - Wrapped a) convBinOp op x y = pure op * x * y I think this is fundamentally different. As I said above: The point is, of course, that such conversions are not only possible for binary operations but for arbitrary values and that these conversions are done by a single generic function conv. Your applicative functor Wrapped allows conversions only for n-ary functions, so, for example, John Meachem’s trick to break the invariant of Set doesn’t work. On the other hand, you need a separate conversion function for each arity (pure, fmap, liftA2, liftA3, …) whereas generalized newtype deriving allows you to use the same conversion function for all arities. Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: more thoughts on Finally tagless
Hi Oleg, On 9 Mar 2010, at 17:52, o...@okmij.org wrote: Stephen Tetley wrote: The finally tagless style is an implementation of the TypeCase pattern (Bruno C. d. S. Oliveira and Jeremy Gibbons): http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/typecase.pdf The finally tagless style is slightly more general. The TypeCase paper emphasizes that TypeCase is a pattern to define a _closed_ type-indexed function -- the indexed family is fixed but the collection of functions is extensible. This is in contrast to type classes, where the collection of functions is fixed (by the class declaration) but the indexed family is extensible (more type class instances can be defined at any time). The tagless final approach permits the definition of an extensible family of open type-indexed functions. For example, we can define a `data type' of expressions and extend it at any time with more expression forms *and* more processing functions (e.g., a new way to print or compile an expression). With the tagless final approach, we have the extensibility in both dimensions. It is true that Typecase is aimed at closed type-indexed functions, although in Section 4.2 I note, in passing, that you can achieve extensibility too for the *explicit* representations variation of the typecase pattern (which is the same that is used by tagless final): The smart datatype solution in this section is fully closed to extension. That is, in order to add another case in the formatting list, such as a constructor Chr that handles characters, we would need to modify the GADT itself. On the other hand, the solution in the previous section using the explicit version of the design pattern allows some form of extensibility. Adding a new case for printf that handles characters corresponds to adding a new function, which could even be in a different module. Fortunately, there is a whole paper devoted to the issue of extensibility for an application of the typecase pattern using *explict* representations: Extensible and Modular Generics for the Masses Bruno C. d. S. Oliveira, Ralf Hinze and Andres Loeh In Henrik Nilsson, editor, Trends in Functional Programming (TFP). Link: http://ropas.snu.ac.kr/%7Ebruno/papers/ExtensibleGM.pdf And the relation to the expression problem is pointed out there. Perhaps you'd like to have a look at the paper if you haven't seen it already. Bruno ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] generalized newtype deriving allows the definition of otherwise undefinable functions
| some time ago, it was pointed out that generalized newtype deriving could be | used to circumvent module borders. Now, I found out that generalized newtype | deriving can even be used to define functions that would be impossible to define | otherwise. To me, this is surprising since I thought that generalized newtype | deriving was only intended to save the programmer from writing boilerplate | code, not to extend expressiveness. Yes indeed. See http://hackage.haskell.org/trac/ghc/ticket/1496 for why this is really a bug in general. The trouble described there really happens when 'item' (in your iso class) in instantiated to a data type with a constructor whose fields use type functions. Stephanie Weirich, Steve Zdancewic, Dimitrios Vytiniotis and I have been working hard on a development of the FC intermediate language, and hence of the source language, that will close this (embarrassing) loophole, and allow some new expressiveness. Nothing written down in a form that someone other than us can make sense of, but there will be! In brief, though, we're going to end up with kinds looking like * = * as well as the existing * - * The new form means a type-indexed function whereas the latter means a type-parametric function. John Meacham's example is also very interesting. Even if the data type doesn't use type functions, it might have invariants concerning type classes (his example is Set), and converting all the elements might destroy the invariants. Excellent point! There's no type-soundness issue (no run-time seg fault) but something nearly as bad. Will have to think about that. Probably declaring Set to have kind (* = *) will do the job. Thanks for the thread. Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] more thoughts on Finally tagless
Tom Schrijvers wrote: Yeah, subject Finally Tagless again, sorry, I'm just not done with it yet. In Olegs haskell implementation he is using classes mainly to model the syntax and instances to use for evaluators / compilers to allow multiple interpretations. I wonder if it'd be possible to do the same without classes using data types instead? Something similar to what Luke Palmer has done here: http://lukepalmer.wordpress.com/2010/01/24/haskell-antipattern-existential-typeclass/ You can just use the dictionary translation of type classes to replace them with data types: E.g. class Eval sem where val :: Int - sem Int add :: sem Int - sem Int - sem Int -- data EvalDict sem = EvalDict { val :: Int - sem Int, add :: sem Int - sem Int - sem Int } This is the way to program in the final tagless style without using type classes, but there is an important difference to what Luke Palmer did in the blog post cited above. While both approaches allow to encode type classes using data types, they are technically different, and applicable for different programs. In the dictionary approach, the dictionary contains fields of the same types as the members of the class. For example, val has the type Int - sem Int in both the type class and the data type. This is not the case in the pattern described by Luke. There, the w type is dropped from the types of the methods when converting to a data type. For example, the type of growHorizontal is w - Bool in the type class, but simply Bool in the data type. The reason for this difference is that Luke uses the fact that w is going to be always existentially bound, so it will not be externally usable anyway. The information contained in the w values can just as well be stored in each of the fields of the data type. The dictionary approach encodes abstract data types: The data type is the interface, each value of the data type is an implementation, and a function which takes the dictionary and is parametric in the type parameters of the dictionary is a program which uses the data type abstractly. For example, a program using the Eval abstract data type from above could look like this: -- using the type class add_two :: Eval sem = sem - sem add_two x = add x (val 2) -- using the dictionary add_two :: EvalDict sem - sem - sem add_two dict x = add dict x (val dict 2) On the other hand, Luke describes an encoding of objects: The data type describes the interface of an object, and each value of that data type is an object, with possibly different implementations of each function in the interface. A program using these objects can invent arbitrary new objects, as long as all fields in the interface are defined. Since abstract data types and objects are fundamentally different, so are these two programming patterns. Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: search Data.Tree.Zipper
Jian Fan wrote: I somehow cannot figure this out. Tree is Foldable so I can use find on it. But how can I use find on TreeLoc? Am I missing something obvious? But what exactly is a TreeLoc? Hoogle doesn't know about it. If you created it yourself, you haven't showed us how you defined it or what you are using it for. In any case, below is one way to simplify the code you posted. It is only a small simplification, but it is about the best I can do without seeing the details of what you are trying to do. Try posting this kind of question to the haskell-beginners mailing list. There are people there who are much better at answering this kind of question. One thing that made it hard to follow your code was your repeated use of loc, one shadowing the other. Try to avoid that. searchTree :: (a - Bool) - TreeLoc a - Maybe (TreeLoc a) searchTree pre rootLoc | pred (getLabel rootLoc) = Just rootLoc | otherwise = do loc - firstChild rootLoc searchTree pred loc `mplus` (right loc = searchTree pred) Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Num instance for Lazy ByteStrings (was: NumLazyByteString Package License)
Henning Thielemann wrote: Is NumLazyByteString a newtype around Bytestring.Lazy that interprets the bit stream represented by the ByteString as integer? Thomas DuBuisson wrote: Not exactly. There is not newtype wrapper. NumLazyByteString is: instance Num L.ByteString where ... Are you absolutely certain that this is the one and only canonical instance that can ever exist that makes sense? Otherwise, please use a newtype wrapper. The reason for this is one of the few remaining major warts in Haskell - that there is absolutely *no way* to prevent the export of instances from a module that you import. So it is considered good practice in current Haskell never to write an instance if anyone has ever published one previously, even if you don't foresee ever using the package in which the instance was defined. Otherwise, someone someday may write code that indirectly depends on both modules in some way, and that code will mysteriously fail to compile. In practice, that implies: never write an unwrapped instance for a datatype that you did not define yourself, and especially not for types that are published and are in common usage, unless you are absolutely certain that your instance is truly canonical and universal. By saying that this is a wart, I am not saying that I think it is a good idea to write more than one instance for the same type intentionally. It is not. But there is no way to prevent it from ever happening inadvertently. So it is important for there to be a mechanism to prevent the import of an unwanted instance when that comes up. Your desire to write this instance is yet another case that demonstrates why this is clearly a wart. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generalized newtype deriving allows the definition of otherwise undefinable functions
Am Dienstag, 9. März 2010 11:53:14 schrieben Sie: Isn't this just an extension of the notion that multi-parameter typeclasses without functional dependencies or type families are dangerous and allow for type-naughtiness? Multi-parameter typeclasses are dangerous? It’s the first time I hear that. Could you elaborate, please? Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generalized newtype deriving allows the definition of otherwise undefinable functions
On Mar 9, 2010, at 5:26 AM, Simon Peyton-Jones wrote: ... Stephanie Weirich, Steve Zdancewic, Dimitrios Vytiniotis and I have been working hard on a development of the FC intermediate language, and hence of the source language, that will close this (embarrassing) loophole, and allow some new expressiveness. Nothing written down in a form that someone other than us can make sense of, but there will be! In brief, though, we're going to end up with kinds looking like * = * as well as the existing * - * The new form means a type-indexed function whereas the latter means a type-parametric function. John Meacham's example is also very interesting. Even if the data type doesn't use type functions, it might have invariants concerning type classes (his example is Set), and converting all the elements might destroy the invariants. Excellent point! There's no type-soundness issue (no run-time seg fault) but something nearly as bad. Will have to think about that. Probably declaring Set to have kind (* = *) will do the job. It occurs to me to observe: if we give class constraints in data types some force, and write: data Ord a = Set a = ...[internals go here]... Would this be enough to cue us that Set has a more interesting kind than just * - * ? -Jan-Willem Maessen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generalized newtype deriving allows the definition of otherwise undefinable functions
On Mar 9, 2010, at 5:53 AM, Max Cantor wrote: Isn't this just an extension of the notion that multi-parameter typeclasses without functional dependencies or type families are dangerous and allow for type-naughtiness? I wondered the same thing, but came up with an analogous problematic case that *only* uses generalized newtype deriving: {-# LANGUAGE GeneralizedNewtypeDeriving #-} module Main(main) where import Data.Set class IsoInt a where stripToInt :: item a - item Int convFromInt :: item Int - item a instance IsoInt Int where stripToInt = id convFromInt = id newtype Down a = Down a deriving (Eq, Show, IsoInt) instance Ord a = Ord (Down a) where compare (Down a) (Down b) = compare b a asSetDown :: Set (Down Int) - Set (Down Int) asSetDown = id a1 = toAscList . asSetDown . convFromInt . fromAscList $ [0..10] a2 = toAscList . asSetDown . fromAscList . reverse . convFromInt $ [0..10] main = do print a1 print a2 -Jan-Willem Maessen___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mini-announce: AC-Color 1.1.3
Andrew Coppin wrote: I just uploaded a new version of the AC-Colour package... Thanks for this. Your algorithm for scaling brightness is not correct however. The RGB values in all popular image formats are not linear. They use a gamma transfer function. So your algorithm will indeed change the colors in an image, not just its brightness. In some cases the change in color can be quite drastic. For a long-winded explanation and many examples, see: http://www.4p8.com/eric.brasseur/gamma.html You may want to implement one of the popular gamma transfer functions, such as BT.709 or sRGB. The former may also be useful for your AC-PPM package, since the PPM image format uses it, as specified in its documentation: http://netpbm.sourceforge.net/doc/ppm.html sRGB is used in most other popular image formats on the web nowadays. Colour maps. Give it some control points, and it'll (linearly) interpolate between them Your algorithm for this is actually not linear at all, since RGB values are generally not linear, as above. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generalized newtype deriving allows the definition of otherwise undefinable functions
Isn't this just an extension of the notion that multi-parameter typeclasses without functional dependencies or type families are dangerous and allow for type-naughtiness? On Mar 9, 2010, at 5:45 AM, Wolfgang Jeltsch wrote: Hello, some time ago, it was pointed out that generalized newtype deriving could be used to circumvent module borders. Now, I found out that generalized newtype deriving can even be used to define functions that would be impossible to define otherwise. To me, this is surprising since I thought that generalized newtype deriving was only intended to save the programmer from writing boilerplate code, not to extend expressiveness. Have a look at the following code: {-# LANGUAGE GeneralizedNewtypeDeriving, MultiParamTypeClasses, FlexibleInstances #-} class Iso a b where conv :: item a - item b instance Iso a a where conv = id newtype Wrapped a = Wrap a deriving (Iso a, Show) Now any value whose type contains some type t can be converted into a value of the type that you get if you replace t by Wrap t. Here is some code to demonstrate this for binary operations: newtype BinOp a = BinOp (a - a - a) convBinOp :: (a - a - a) - (Wrapped a - Wrapped a - Wrapped a) convBinOp op = let BinOp op' = conv (BinOp op) in op' Now, you can enter convBinOp (*) (Wrap 5) (Wrap 3) into GHCi, and you will get Wrap 15 as the result. The point is, of course, that such conversions are not only possible for binary operations but for arbitrary values and that these conversions are done by a single generic function conv. I don’t think it would be possible to implement conv without generalized newtype deriving. Any thoughts? Best wishes, Wolfgang ___ 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] Type variables
Hi everyone, this is my first post: I am a ph.d. student from Italy who is learning the wonderful world of Haskell :) I have encountered a problem and I cannot find a way to get past it (or even to begin to understand it). I wish to define a simple type class that defines how to convert a type function into its argument (like going from a dumb constructor like data T a = T a into a itself): class Convert rec where convert :: rec a - a now when I try to use the conversion operator class (CNum n, HasField n (a - (b,rec a)) l, Convert rec) = HasMethod n l a b rec where (..!) :: l - n - (a - (b,a)) instance (CNum n, HasField n (a - (b,rec a)) l, Convert rec) = HasMethod n l a b rec where l ..! n = let m = l .! n in (\x - let (y,v) = m x in (y,convert v)) in what looks to me as a straightforward use, the compiler complains that : *References :load Main.hs [1 of 5] Compiling Records ( Records.hs, interpreted ) [2 of 5] Compiling References ( References.hs, interpreted ) [3 of 5] Compiling Methods ( Methods.hs, interpreted ) Methods.hs:25:14: Could not deduce (HasField n (a - (b, rec a)) l) from the context (HasMethod n l a b rec1, CNum n, HasField n (a - (b, rec1 a)) l, Convert rec1) arising from a use of `.!' at Methods.hs:25:14-19 Possible fix: add (HasField n (a - (b, rec a)) l) to the context of the instance declaration or add an instance declaration for (HasField n (a - (b, rec a)) l) In the expression: l .! n In the definition of `m': m = l .! n In the expression: let m = l .! n in (\ x - let (y, v) = ... in (y, convert v)) Failed, modules loaded: References, Records. *References I apologize for what might look like a huge dumping of code, but I have no idea what might have caused this to further refine the code or to write a more focused example... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generalized newtype deriving allows the definition of otherwise undefinable functions
Am Dienstag, 9. März 2010 15:54:16 schrieb Jan-Willem Maessen: On Mar 9, 2010, at 5:53 AM, Max Cantor wrote: Isn't this just an extension of the notion that multi-parameter typeclasses without functional dependencies or type families are dangerous and allow for type-naughtiness? I wondered the same thing, but came up with an analogous problematic case that *only* uses generalized newtype deriving: […] Originally, I had a more restricted example in mind which is similar to yours. However, I wanted to generalize the problem and therefore introduced the general Iso class which made MultiParamTypeClasses and FlexibleInstances necessary. The actual problem is related neither to MultiParamTypeClasses nor to FlexibleInstances. Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generalized newtype deriving allows the definition of otherwise undefinable functions
On Tue, Mar 09, 2010 at 09:56:45AM -0500, Jan-Willem Maessen wrote: It occurs to me to observe: if we give class constraints in data types some force, and write: data Ord a = Set a = ...[internals go here]... Would this be enough to cue us that Set has a more interesting kind than just * - * ? Yes. I was thinking something along the same lines. Could this just be another example of contravariance flipping the meaning of quantification? If we take the simpler example given: class Iso a where conv :: item a - item Int let's give the whole type class Iso a where conv :: forall (item :: * - *) . item a - item Int It seems to me the issue may not be with newtype deriving, but with that universal quantification over a type constructor. If we were to declare 'Set' like so data Ord a = Set a = ... like Jan-Willem suggests, then it seems that 'Set' should not be able to unify with 'item' since it has the extra 'Ord' consraint on the contravariant argument to item and item is universally quantified. Item would need a psuedo-type like (Ord a = item :: a - *) to match. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: A few ideas about FRP and arbitrary access in time
On 2010-03-08, Brandon S. Allbery KF8NH allb...@ece.cmu.edu wrote: There is a discrete time quantum. But unless you're doing simulations at the quantum level, you really don't want to go there (even ignoring that one second of real time would take a really long time to calculate on current hardware :); stick to macrocosmic physics, which is statistically continuous. That's ... contentious. In both quantum mechanics and GR, time is completely, flattly, continuous. In certain extremely speculative frameworks attempting to combine the regimes in which they are applicable, that may not be the case. But for accepted physics models, time really is continous. -- Aaron Denney -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: generalized newtype deriving allows the definition of otherwise undefinable functions
On Mon, 2010-03-08 at 23:32 +0100, Wolfgang Jeltsch wrote: For example, with the above conv method, you could probably convert a list of some type [t] into a list of type [Wrapped t] in O(1) time. If you would code this conversion by hand, it would take O(n) time, of course. Wouldn't timing be exactly the same? I mean: (map Wrapped xs) !! k and (conv xs :: [Wrapped t]) !! k They have exactly the same 'complexity' - O(k) (if k is constant we have constant time access - even if list is infinite). The 'problem' is that if you combine O(f) algorithm and O(g) algorithm resulting complexity is somewhere in between. For example head (O(1)) combined with sort (O(n log n)) gives us O(n) complexity. Map have nice property that combined it 'borrows' complexity from another algorithm. So g . map f have complexity of g (if f have O(1) of course). I don't see any benefits of conv as: - If the conversion is valid it is usually provided (see for example mapMonotonic). Unfortunately Set is strict but I guess it belongs to compiler optimization then conv function[1] - If conversion is not valid it should not be performed in the first place. Regards [1] I don't know maybe something like: {-# RULES mapMonotonic/iso mapMonotonic ISO = unsafeCoerce #-} When ISO is special value which indicate newtype constructor (example keyword). It is up to programmer (library or user - here user as it is in preconditions) to assure that conversion is safe. As in example given in other post Wrapped is not monotonic it cannot be used argument as mapMonotonic (ok. due to precondition but still). signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: search Data.Tree.Zipper
Well, TreeLoc comes from Data.Tree.Zipper which comes from rosezipper packge. Thank you and MightyByte. Its much improved now. Jian Yitzchak Gale g...@sefer.org wrote: Jian Fan wrote: I somehow cannot figure this out. Tree is Foldable so I can use find on it. But how can I use find on TreeLoc? Am I missing something obvious? But what exactly is a TreeLoc? Hoogle doesn't know about it. If you created it yourself, you haven't showed us how you defined it or what you are using it for. In any case, below is one way to simplify the code you posted. It is only a small simplification, but it is about the best I can do without seeing the details of what you are trying to do. Try posting this kind of question to the haskell-beginners mailing list. There are people there who are much better at answering this kind of question. One thing that made it hard to follow your code was your repeated use of loc, one shadowing the other. Try to avoid that. searchTree :: (a - Bool) - TreeLoc a - Maybe (TreeLoc a) searchTree pre rootLoc | pred (getLabel rootLoc) = Just rootLoc | otherwise = do loc - firstChild rootLoc searchTree pred loc `mplus` (right loc = searchTree pred) Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type variables
On Tue, 2010-03-09 at 15:50 +0100, Giuseppe Maggiore wrote: class (CNum n, HasField n (a - (b,rec a)) l, Convert rec) = HasMethod n l a b rec where (..!) :: l - n - (a - (b,a)) instance (CNum n, HasField n (a - (b,rec a)) l, Convert rec) = HasMethod n l a b rec where l ..! n = let m = l .! n in (\x - let (y,v) = m x in (y,convert v)) i think you have in mind something like: import Control.Arrow (..!) :: (CNum n, HasField n (a - (b,rec a)) l, Convert rec) = l - n - (a - (b,a)) l ..! n = second convert . (l .! n) 1. I don't see a point of creating class. I mean you provide a wildcard implementation - why not provide just a method? 2. I'm afraid that it might be monomorphism restriction. But I'm not sure. 3. Without code I can hardly test the problems ;) I can write what I _think_ code would look like. Regards PS. I would be grateful for ASCII-only posts: http://www.asciiribbon.org/ PPS. convert looks strangly similar to copointed: http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Functor-Pointed.html#t%3ACopointed signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Type variables
Thanks, that helped (monomorphism restriction and copointed)... I'll see if I can come up with a more specific example! On Tue, Mar 9, 2010 at 6:12 PM, Maciej Piechotka uzytkown...@gmail.comwrote: On Tue, 2010-03-09 at 15:50 +0100, Giuseppe Maggiore wrote: class (CNum n, HasField n (a - (b,rec a)) l, Convert rec) = HasMethod n l a b rec where (..!) :: l - n - (a - (b,a)) instance (CNum n, HasField n (a - (b,rec a)) l, Convert rec) = HasMethod n l a b rec where l ..! n = let m = l .! n in (\x - let (y,v) = m x in (y,convert v)) i think you have in mind something like: import Control.Arrow (..!) :: (CNum n, HasField n (a - (b,rec a)) l, Convert rec) = l - n - (a - (b,a)) l ..! n = second convert . (l .! n) 1. I don't see a point of creating class. I mean you provide a wildcard implementation - why not provide just a method? 2. I'm afraid that it might be monomorphism restriction. But I'm not sure. 3. Without code I can hardly test the problems ;) I can write what I _think_ code would look like. Regards PS. I would be grateful for ASCII-only posts: http://www.asciiribbon.org/ PPS. convert looks strangly similar to copointed: http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Functor-Pointed.html#t%3ACopointed ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Giuseppe Maggiore Ph.D. Student (Languages and Games) Microsoft Student Partner Mobile: +393319040031 Office: +390412348444 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: A few ideas about FRP and arbitrary access in time
On Tue, Mar 09, 2010 at 05:23:56AM +, Aaron Denney wrote: On 2010-03-08, Brandon S. Allbery KF8NH allb...@ece.cmu.edu wrote: There is a discrete time quantum. But unless you're doing simulations at the quantum level, you really don't want to go there (even ignoring that one second of real time would take a really long time to calculate on current hardware :); stick to macrocosmic physics, which is statistically continuous. That's ... contentious. In both quantum mechanics and GR, time is completely, flattly, continuous. In certain extremely speculative frameworks attempting to combine the regimes in which they are applicable, that may not be the case. But for accepted physics models, time really is continous. Hmm.. I thought something interesting happened on the scale of the plank time, 10^-44 seconds or so. Or is that only relevant to our ability to _measure_ things at that scale and not the continuity of time itself as far as QM is concerned? John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Num instance for Lazy ByteStrings (was: NumLazyByteString Package License)
On Mar 9, 2010, at 09:41 , Yitzchak Gale wrote: Henning Thielemann wrote: Is NumLazyByteString a newtype around Bytestring.Lazy that interprets the bit stream represented by the ByteString as integer? Thomas DuBuisson wrote: Not exactly. There is not newtype wrapper. NumLazyByteString is: instance Num L.ByteString where ... Are you absolutely certain that this is the one and only canonical instance that can ever exist that makes sense? Otherwise, please use a newtype wrapper. Or from the other direction: you're in essence declaring that *any* ByteString can be used as a Num, etc. This strikes me as inviting confusion, at the very least; I'd strongly prefer the type system to help me distinguish ByteStrings used as Nums from those used as Strings, instead of quietly doing unexpected things (or issuing odd type errors) because I accidentally passed the wrong argument. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon universityKF8NH PGP.sig Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] First time haskell - parse error!
Hi, i am getting an error when trying to compile this part of my program, its my first time using haskell and as lovely as it is it didn't give me very much to go on in the error message! codescore :: String - String - String score [s] [] = false score [s] [g] = if valid 4 g then (s1 ++ s2 ++ s3 ++ s4) where s1 = Golds s2 = show (gold s g) s3 = , Silvers s4 = show (silver s g) else Bad Guess/code when i try to compile it says: test.hs 63:29: parse error on input 'where' (its the line beginning with 'then') Anybody got any ideas whats going on? thanks! -- View this message in context: http://old.nabble.com/First-time-haskell---parse-error%21-tp27839657p27839657.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] First time haskell - parse error!
2010/3/9 boblettoj bobletto...@msn.com: Hi, i am getting an error when trying to compile this part of my program, its my first time using haskell and as lovely as it is it didn't give me very much to go on in the error message! codescore :: String - String - String score [s] [] = false score [s] [g] = if valid 4 g then (s1 ++ s2 ++ s3 ++ s4) where s1 = Golds s2 = show (gold s g) s3 = , Silvers s4 = show (silver s g) else Bad Guess/code when i try to compile it says: test.hs 63:29: parse error on input 'where' (its the line beginning with 'then') Anybody got any ideas whats going on? thanks! -- View this message in context: http://old.nabble.com/First-time-haskell---parse-error%21-tp27839657p27839657.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe You can't use `where' in the middle of an `if'. This should get rid of the parse error: score :: String - String - String score [s] [] = false score [s] [g] = if valid 4 g then (s1 ++ s2 ++ s3 ++ s4) else Bad Guess where s1 = Golds s2 = show (gold s g) s3 = , Silvers s4 = show (silver s g) -- Deniz Dogan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] First time haskell - parse error!
Thats because you can't put a where in a then clause. Move the where stuff to the end of the function. On 09/03/10 19:04, boblettoj wrote: Hi, i am getting an error when trying to compile this part of my program, its my first time using haskell and as lovely as it is it didn't give me very much to go on in the error message! codescore :: String - String - String score [s] [] = false score [s] [g] = if valid 4 g then (s1 ++ s2 ++ s3 ++ s4) where s1 = Golds s2 = show (gold s g) s3 = , Silvers s4 = show (silver s g) else Bad Guess/code when i try to compile it says: test.hs 63:29: parse error on input 'where' (its the line beginning with 'then') Anybody got any ideas whats going on? thanks! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: generalized newtype deriving allows the definition of otherwise undefinable functions
On Tuesday 09 March 2010 9:36:51 am Maciej Piechotka wrote: On Mon, 2010-03-08 at 23:32 +0100, Wolfgang Jeltsch wrote: For example, with the above conv method, you could probably convert a list of some type [t] into a list of type [Wrapped t] in O(1) time. If you would code this conversion by hand, it would take O(n) time, of course. Wouldn't timing be exactly the same? I mean: (map Wrapped xs) !! k and (conv xs :: [Wrapped t]) !! k They have exactly the same 'complexity' - O(k) (if k is constant we have constant time access - even if list is infinite). Comparing the complexity isn't really going to tell you which of these does more work. If n is O(m), then an algorithm that takes 'm + n' steps has the same overall complexity as one that simply takes 'm' steps, but obviously the first does more work. The difference (in work) between map Wrapped and conv is the difference between map id and id :: [a] - [a]. In the absence of any fusion/rewrite rules, the former breaks down a list, and builds up a new one with exactly the same elements (or, every element x becomes an id x thunk, perhaps). So, in a lazy language, inspecting each cons cell carries an additional O(1) overhead over inspecting the corresponding cons cell in the original list (because inspecting the former implicitly inspects the latter, and then yields a new cons cell with the same values for inspection). So, if 'id xs !! k' takes costs f(k), then 'map id xs !! k' costs f(k) + C*k. Both are O(k), but the latter is more expensive. -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: generalized newtype deriving allows the definition of otherwise undefinable functions
On Tue, Mar 09, 2010 at 02:16:11PM -0500, Dan Doel wrote: The difference (in work) between map Wrapped and conv is the difference between map id and id :: [a] - [a]. In the absence of any fusion/rewrite rules, the former breaks down a list, and builds up a new one with exactly the same elements (or, every element x becomes an id x thunk, perhaps). So, in a lazy language, inspecting each cons cell carries an additional O(1) overhead over inspecting the corresponding cons cell in the original list (because inspecting the former implicitly inspects the latter, and then yields a new cons cell with the same values for inspection). So, if 'id xs !! k' takes costs f(k), then 'map id xs !! k' costs f(k) + C*k. Both are O(k), but the latter is more expensive. Not to mention they can have radically different space usages. xs = 'x':xs id xs = constant space map id xs = potentially infinite space John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] First time haskell - parse error!
On 9 mrt 2010, at 20:04, boblettoj wrote: Hi, i am getting an error when trying to compile this part of my program, its my first time using haskell and as lovely as it is it didn't give me very much to go on in the error message! codescore :: String - String - String score [s] [] = false score [s] [g] = if valid 4 g then (s1 ++ s2 ++ s3 ++ s4) where s1 = Golds s2 = show (gold s g) s3 = , Silvers s4 = show (silver s g) else Bad Guess/code If you want to keep the definitions local to the expression you should write then let s1 = .. s2 = ... ... in (s1++s2++s3++s4) else ... Doaitse when i try to compile it says: test.hs 63:29: parse error on input 'where' (its the line beginning with 'then') Anybody got any ideas whats going on? thanks! -- View this message in context: http://old.nabble.com/First-time-haskell---parse-error%21-tp27839657p27839657.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: search Data.Tree.Zipper
Thanks. `mplus` is the glue I was looking for. The original algorithm has a bug. Following is what I have for now: searchTree pred rootLoc | pred (getLabel rootLoc) = Just rootLoc | otherwise = (right rootLoc = searchTree pred) `mplus` (firstChild rootLoc = searchTree pred) Jian MightyByte mightyb...@gmail.com wrote: I haven't tested it, but I think you're looking for something like this: searchTree2 :: (a - Bool) - TreeLoc a - Maybe (TreeLoc a) searchTree2 pred rootLoc = if pred (getLabel rootLoc) then Just rootLoc else firstChild rootLoc = siblings where siblings loc = searchTree2 pred loc `mplus` (searchTree2 pred = right loc) On Mon, Mar 8, 2010 at 1:11 PM, Jian Fan abe...@gmail.com wrote: Hi, There doesn't seem to be a function to search the tree so I come up with following function: searchTree :: (a - Bool) - TreeLoc a - Maybe (TreeLoc a) searchTree pred rootLoc = if pred (getLabel rootLoc) then Just rootLoc else case firstChild rootLoc of Just loc - case searchTree pred loc of Just loc - Just loc Nothing - case right loc of Just rLoc - searchTree pred rLoc Nothing - Nothing Nothing - Nothing Which feels quite ugly. Any suggestions? Thanks. Jian ___ 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] First time haskell - parse error!
On 09.03.2010 20:04, boblettoj wrote: score :: String - String - String score [s] [] = false score [s] [g] = if valid 4 g then (s1 ++ s2 ++ s3 ++ s4) where s1 = Golds s2 = show (gold s g) s3 = , Silvers s4 = show (silver s g) else Bad Guess Apart from the parse error there is also a type error in your code: When the second argument is empty, you return false although you declared the function to return a String, not a boolean. Also you require the first argument to be a string containing exactly one character and the second argument to be a string containing zero or one characters. I'm not quite sure that's what you intend. If it is, you should consider changing the function so that it takes a Char and a Maybe Char, instead of two strings. HTH, Sebastian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: generalized newtype deriving allows the definition of otherwise undefinable functions
The difference (in work) between map Wrapped and conv is the difference between map id and id :: [a] - [a]. In the absence of any fusion/rewrite rules, the former breaks down a list, and builds up a new one with exactly the same elements (or, every element x becomes an id x thunk, perhaps). So, in a lazy language, inspecting each cons cell carries an additional O(1) overhead over inspecting the corresponding cons cell in the original list (because inspecting the former implicitly inspects the latter, and then yields a new cons cell with the same values for inspection). On a related note, I've been occasionally worried about conversions like 'map convert huge' where 'convert' is from one newtype to another with the same underlying type. I tried some simple examples and looking at core it seems like the 'map id huge' is optimized away. However, I'm guessing that's only because of a 'map id xs - id xs' rewrite rule involved, and it won't work for all data structures. It seems like a better solution than relying on rewrite rules would be to lift the newtype up one level, e.g. convert 'M (Newtype x)' to 'Newtype (M x)'. Actually what I really want is to replace every function that goes M x - x with M x - Newtype x, but we don't have parameterized modules and doing this for something like Data.Map means a lot of boilerplate. Surely there is some more general approach? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] vector stream fusion, inlining and compilation time
I think Jake is referring to my vector-space package. He did the work of writing 171 INLINE pragmas, covering lots of methods and standalone function defs. I'm simultaneously grateful for the effort and repelled by the added syntactic noise. Also concerned about the impact of all these directives on other uses of vector-space. If all this inlining is a uniform win, I'd rather ghc did it for me. If the ghc implementers have reasons not to do so in general, then I'd expect that some of those reasons apply to vector-space (and many other libraries) as well. It's not like I'm applying some kind of domain-specific understanding that ghc doesn't have access to. I'm raising my concerns here in the hopes of stimulating some creative thinking and suggestions about addressing this sort of situation more generally. - Conal On Sun, Mar 7, 2010 at 9:23 PM, Don Stewart d...@galois.com wrote: jake.mcarthur: I've run into an issue with inlining that I'm not sure how to work around. I am instantiating some pre-existing type classes with Vector-based types. There already exist generic functions in modules I do not control that use this type class, and they are not tagged with the INLINE pragma. I am doubtful, but I figure it is worth at least asking: is there some practical workaround for this kind of situation that anybody knows about? I don't know of a way, other than patching the library code. If it makes a difference to you, it probably makes a difference to lots of people. -- Don ___ 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: A few ideas about FRP and arbitrary access in time
John Meacham wrote: On Tue, Mar 09, 2010 at 05:23:56AM +, Aaron Denney wrote: On 2010-03-08, Brandon S. Allbery KF8NH allb...@ece.cmu.edu wrote: There is a discrete time quantum. But unless you're doing simulations at the quantum level, you really don't want to go there (even ignoring that one second of real time would take a really long time to calculate on current hardware :); stick to macrocosmic physics, which is statistically continuous. That's ... contentious. In both quantum mechanics and GR, time is completely, flattly, continuous. In certain extremely speculative frameworks attempting to combine the regimes in which they are applicable, that may not be the case. But for accepted physics models, time really is continous. Hmm.. I thought something interesting happened on the scale of the plank time, 10^-44 seconds or so. Or is that only relevant to our ability to _measure_ things at that scale and not the continuity of time itself as far as QM is concerned? It may sound strange, but continuous quantities are often an approximation. For instance, a bar of steel is composed of a finite number of atoms, but if you want to know how it behaves under load (theory of elasticity), you can model it as a continuous mass just fine because the number of atoms is huge. Same goes for time. It doesn't really matter what happens in minuscule time scale; for the purpose of Newtonian mechanics, time is continuous. (It's continuous for the purpose of modeling more fundamental theories as well.) The key point is that this is not absolute reality, it's just a model. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: A few ideas about FRP and arbitrary access in time
On Mar 9, 2010, at 9:34 AM, John Meacham wrote: Hmm.. I thought something interesting happened on the scale of the plank time, 10^-44 seconds or so. Or is that only relevant to our ability to _measure_ things at that scale and not the continuity of time itself as far as QM is concerned? Quantum mechanics itself does not have a natural time scale at which interesting things start to happen, but some theories built using quantum mechanics do. It helps if you think of quantum mechanics as being like Newton's laws: it is not a theory itself so much as a metatheory that provides ground rules for how to construct theories of nature. (And yes, I actually am a quantum physicist. :-) ) Cheers, Greg ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: search Data.Tree.Zipper
Jian Fan wrote: Following is what I have for now... Oh, nice! That is simpler. Now we can do: searchTree pred rootLoc | pred (getLabel rootLoc) = Just rootLoc | otherwise = search right `mplus` search firstChild where search next = next rootLoc = searchTree pred Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generalized newtype deriving allows the definition of otherwise undefinable functions
I am pretty sure this problem is known, but you should add this code to the bug report: http://hackage.haskell.org/trac/ghc/ticket/1496 -- ryan On Tue, Mar 9, 2010 at 6:54 AM, Jan-Willem Maessen jmaes...@alum.mit.edu wrote: On Mar 9, 2010, at 5:53 AM, Max Cantor wrote: Isn't this just an extension of the notion that multi-parameter typeclasses without functional dependencies or type families are dangerous and allow for type-naughtiness? I wondered the same thing, but came up with an analogous problematic case that *only* uses generalized newtype deriving: {-# LANGUAGE GeneralizedNewtypeDeriving #-} module Main(main) where import Data.Set class IsoInt a where stripToInt :: item a - item Int convFromInt :: item Int - item a instance IsoInt Int where stripToInt = id convFromInt = id newtype Down a = Down a deriving (Eq, Show, IsoInt) instance Ord a = Ord (Down a) where compare (Down a) (Down b) = compare b a asSetDown :: Set (Down Int) - Set (Down Int) asSetDown = id a1 = toAscList . asSetDown . convFromInt . fromAscList $ [0..10] a2 = toAscList . asSetDown . fromAscList . reverse . convFromInt $ [0..10] main = do print a1 print a2 -Jan-Willem Maessen___ 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] vector stream fusion, inlining and compilation time
On Tue, Mar 9, 2010 at 11:53 AM, Conal Elliott co...@conal.net wrote: I think Jake is referring to my vector-space package. He did the work of writing 171 INLINE pragmas, covering lots of methods and standalone function defs. I'm simultaneously grateful for the effort and repelled by the added syntactic noise. Also concerned about the impact of all these directives on other uses of vector-space. If all this inlining is a uniform win, I'd rather ghc did it for me. Alas, it very much is not easy to predict. The unfortunate thing about inline directives is that each individual one really can have a substantial, but not necessarily predictable, effect on the performance of an application. I have seen large improvements in performance, large drops in performance, nothing at all, and everything in between, and I have yet to develop a consistently successful intuition about what will work well, and when. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] First time haskell - parse error!
On Tue, Mar 09, 2010 at 08:42:44PM +0100, Sebastian Hungerecker wrote: On 09.03.2010 20:04, boblettoj wrote: score :: String - String - String score [s] [] = false score [s] [g] = if valid 4 g then (s1 ++ s2 ++ s3 ++ s4) where s1 = Golds s2 = show (gold s g) s3 = , Silvers s4 = show (silver s g) else Bad Guess Apart from the parse error there is also a type error in your code: When the second argument is empty, you return false although you declared the function to return a String, not a boolean. Not quite; data Bool = True | False, and the code uses a lowercase 'f' 'false'. Perhaps 'false' is defined as a String somewhere else? A bit odd, perhaps, but not necessarily a type error. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] First time haskell - parse error!
Seems like a good time to mention the Maybe monad looks like it would be a good fit here. score :: String - String - Maybe String score s [] = Nothing score s g = if valid 4 g then let s1 = Golds s2 = show (gold s g) s3 = , Silvers s4 = show (silver s g) in Just (s1 ++ s2 ++ s3 ++ s4) else Just Bad Guess -R. Kyle Murphy -- Curiosity was framed, Ignorance killed the cat. On Tue, Mar 9, 2010 at 17:42, Brent Yorgey byor...@seas.upenn.edu wrote: On Tue, Mar 09, 2010 at 08:42:44PM +0100, Sebastian Hungerecker wrote: On 09.03.2010 20:04, boblettoj wrote: score :: String - String - String score [s] [] = false score [s] [g] = if valid 4 g then (s1 ++ s2 ++ s3 ++ s4) where s1 = Golds s2 = show (gold s g) s3 = , Silvers s4 = show (silver s g) else Bad Guess Apart from the parse error there is also a type error in your code: When the second argument is empty, you return false although you declared the function to return a String, not a boolean. Not quite; data Bool = True | False, and the code uses a lowercase 'f' 'false'. Perhaps 'false' is defined as a String somewhere else? A bit odd, perhaps, but not necessarily a type error. -Brent ___ 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] more thoughts on Finally tagless
Tom Schrijvers wrote: data EvalDict sem = EvalDict { val :: Int - sem Int, add :: sem Int - sem Int - sem Int } An alternative option is to capture the structure in a GADT: data Eval a where Val :: Int - Eval Int Add :: Eval Int - Eval Int - Eval Int And then write what were instances before as functions Eval a - whatever. Of course, this makes it harder to combine multiple models. Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] If the local variable can be changed ...
In FP the variable can not be changed once created. Yes, it has much advantage . However, i feel it is too strict. As we know, the local variable is allocated on stack which is thread safe. So if the local variable can be changed, then we can use loop, etc. same as imperative languages. For example, for (i=0; i100; i++) where `i` is a local variable in function. Any suggestion is appreciated! - fac n = let { f = foldr (*) 1 [1..n] } in f -- View this message in context: http://old.nabble.com/If-the-local-variable-can-be-changed-...-tp27844016p27844016.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] If the local variable can be changed ...
On 10 March 2010 11:25, zaxis z_a...@163.com wrote: So if the local variable can be changed, then we can use loop, etc. same as imperative languages. For example, for (i=0; i100; i++) where `i` is a local variable in function. But why would we want to? That's what folds, etc. are for! -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] If the local variable can be changed ...
If your code performs a common task (such as conversion, accumulation, testing), then you should use higher-level constructs than a for loop. Using map, filter, foldr, and foldl will make it easier to write correct code. If you'd like to imitate a for loop exactly -- that is, to perform some action multiple times -- it's very easy to create a pure function. We do not have to stoop to mutable variables. - for :: Monad m = a - (a - Bool) - (a - a) - (a - m ()) - m () for start test step body = loop start where loop x = if test x then body x loop (step x) else return () main = for 0 ( 100) (+ 1) $ \i - do -- do something with i print i - On Tue, Mar 9, 2010 at 16:25, zaxis z_a...@163.com wrote: In FP the variable can not be changed once created. Yes, it has much advantage . However, i feel it is too strict. As we know, the local variable is allocated on stack which is thread safe. So if the local variable can be changed, then we can use loop, etc. same as imperative languages. For example, for (i=0; i100; i++) where `i` is a local variable in function. Any suggestion is appreciated! - fac n = let { f = foldr (*) 1 [1..n] } in f -- View this message in context: http://old.nabble.com/If-the-local-variable-can-be-changed-...-tp27844016p27844016.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] 3rd party widgets with qtHaskell (Marble)
Hi, I know this isn't a qtHaskell list, but I don't think there is one. Was wondering if anyone has any ideas on the below. Basically I'm trying to control a Marble (Map software) Qt widget from qtHaskell. So I've mocked up a very simple user interface in Qt Designer (1 form, 1 Marble widget). I can load this up and display it fine in Haskell, but as soon as I try to interrogate the widget I get a seg fault (eg qObjectProperty) My guess is that the call to findChild, although it executes OK it is not producing a valid QObject - probably casting to Marble::MarbleWidget* it crux of the problem. I can get this working using standard Qt Widgets (just like the examples show from qtHaskell), so I know the method is sound - although calling 3rd party widgets like this may be ambitious or impossible. I recognise this is a fairly broad query! Has anyone tried anything similar? Is it even possible to do this in qtHaskell as I'm proposing? I'm a Qt novice, so it may well be that I've misunderstood qtHaskell. Cheers, Phil. Using: GHC 6.12.1 / QT4.5 / Marble 0.8 / Ubuntu 9.04 module Main where import Qtc main :: IO () main = do app - qApplication () rok - registerResource marble.rcc loader - qUiLoader () uiFile - qFile :/marble.ui open uiFile fReadOnly ui - load loader uiFile close uiFile () ui_map - findChild ui (Marble::MarbleWidget*, MarbleWidget) sc - qObjectProperty ui_map showCompass qshow ui () ok - qApplicationExec () return () ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] If the local variable can be changed ...
Yes, we can imitate all of it (such as `when`, `until` and `for`) because haskell is a good DSL language. However, i feel it will be more convenient if the language itself supports all these fundations. jmillikin wrote: If your code performs a common task (such as conversion, accumulation, testing), then you should use higher-level constructs than a for loop. Using map, filter, foldr, and foldl will make it easier to write correct code. If you'd like to imitate a for loop exactly -- that is, to perform some action multiple times -- it's very easy to create a pure function. We do not have to stoop to mutable variables. - for :: Monad m = a - (a - Bool) - (a - a) - (a - m ()) - m () for start test step body = loop start where loop x = if test x then body x loop (step x) else return () main = for 0 ( 100) (+ 1) $ \i - do -- do something with i print i - On Tue, Mar 9, 2010 at 16:25, zaxis z_a...@163.com wrote: In FP the variable can not be changed once created. Yes, it has much advantage . However, i feel it is too strict. As we know, the local variable is allocated on stack which is thread safe. So if the local variable can be changed, then we can use loop, etc. same as imperative languages. For example, for (i=0; i100; i++) where `i` is a local variable in function. Any suggestion is appreciated! - fac n = let { f = foldr (*) 1 [1..n] } in f -- View this message in context: http://old.nabble.com/If-the-local-variable-can-be-changed-...-tp27844016p27844016.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe - fac n = let { f = foldr (*) 1 [1..n] } in f -- View this message in context: http://old.nabble.com/If-the-local-variable-can-be-changed-...-tp27844016p27845844.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] If the local variable can be changed ...
On 10 March 2010 16:45, zaxis z_a...@163.com wrote: Yes, we can imitate all of it (such as `when`, `until` and `for`) because haskell is a good DSL language. However, i feel it will be more convenient if the language itself supports all these fundations. You seem to be missing the point of referential transparency [1] and purity [2], something which most of us quite _like_ about Haskell. If you absolutely _need_ mutation within Haskell, see IORefs and the like. [1]: http://en.wikipedia.org/wiki/Referential_transparency_(computer_science) [2]: http://en.wikipedia.org/wiki/Purely_functional -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANN: powerpc-0.0.1
Here is a new library for analyzing PowerPC programs [1]. At this point it does instruction set simulation on machine code -- and not all instructions are implemented yet, BTW. To run a simulation, the user defines an instance of the Memory class [2] to represent both instruction and data memory. The Memory class declares functions for memory loads and stores, instruction fetches, and reading and writing special purpose registers. In our test bench, we set up the 'fetch' method to dump out register values so we can see the state of the processor at every step. A neat feature of the library is the instruction behavior is captured by a little DSL [3]. This makes it easy to add new instructions because the translation from the instruction RTL spec [4] to the DSL is nearly one-to-one. And with instruction behavior captured symbolically, this opens the door to other types of analysis besides just simulation. I hope a few folks find it useful. -Tom [1] http://hackage.haskell.org/package/powerpc [2] http://hackage.haskell.org/packages/archive/powerpc/0.0.1/doc/html/Language-PowerPC-Simulator.html#t%3AMemory [3] http://hackage.haskell.org/packages/archive/powerpc/0.0.1/doc/html/Language-PowerPC-RTL.html [4] http://www.ibm.com/developerworks/systems/library/es-archguide-v2.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: powerpc-0.0.1
Wow. Quite ambitious. Was this inspired by work at your current employer like with Atom and some of the other stuff you've released? Warren On Tue, Mar 9, 2010 at 10:35 PM, Tom Hawkins tomahawk...@gmail.com wrote: Here is a new library for analyzing PowerPC programs [1]. At this point it does instruction set simulation on machine code -- and not all instructions are implemented yet, BTW. To run a simulation, the user defines an instance of the Memory class [2] to represent both instruction and data memory. The Memory class declares functions for memory loads and stores, instruction fetches, and reading and writing special purpose registers. In our test bench, we set up the 'fetch' method to dump out register values so we can see the state of the processor at every step. A neat feature of the library is the instruction behavior is captured by a little DSL [3]. This makes it easy to add new instructions because the translation from the instruction RTL spec [4] to the DSL is nearly one-to-one. And with instruction behavior captured symbolically, this opens the door to other types of analysis besides just simulation. I hope a few folks find it useful. -Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] If the local variable can be changed ...
zaxis wrote: Yes, we can imitate all of it (such as `when`, `until` and `for`) because haskell is a good DSL language. However, i feel it will be more convenient if the language itself supports all these fundations. There is such a language, its called Disciple and its compiler is DDC: http://www.haskell.org/haskellwiki/DDC However, the compiler is an experimental compiler, is still incomplete and has bugs. Erik -- -- Erik de Castro Lopo http://www.mega-nerd.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] First time haskell - parse error!
S. Doaitse Swierstra doai...@cs.uu.nl writes: then (s1 ++ s2 ++ s3 ++ s4) where s1 = Golds s2 = show (gold s g) s3 = , Silvers s4 = show (silver s g) If you want to keep the definitions local to the expression you should write ..but I think it is better style to avoid this kind of one-off named values. I much prefer: then Golds ++show (gold s g)++... For some reason, this is a style isse that doesn't get much attention, at least not in the non-functional language tradition, where temporary variables are scattered all over. So instead of doing: let ns y = not (isSpace y) f x = takeWhile ns x in map f We can use anonymous functions in place of the uninformatively named ones: map (\x - takeWhile (\y - not (isSpace y)) x) and use partial application toward point-free-ness: map (takeWhile (not . isSpace)) which IMO is a lot easier to read, taking up less screen and mind estate. Of course it's possible to overdo the point-free thing (commonly referred to as pointless), but I think it's great when you can eliminate gratuitous naming like this. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe