Re: [Haskell-cafe] ANN: bloxorz clone
Here's a video of bloxorz at work, very cool! http://archhaskell.wordpress.com/2009/07/04/bloxorz-an-opengl-logic-game-written-in-haskell/ I see it wasn't rehearsed in advance. ;) Gergely -- http://www.fastmail.fm - The professional email service ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell Platform 2009.2.0.1 and GLUT32.DLL on Windows: which version?
I know GLUT32.DLL is not bundled with the Haskell Platform installer, but which GLUT32.DLL should I use? Every DLL I tried (even building FreeGLUT myselfhttp://netsuperbrain.com/blog/posts/freeglut-windows-hopengl-hglut/#more-136) gives the error: *The procedure entry point glutAddMenuEntry could not be located in the dynamic library glut32.dll* Any hints as to which glut32 version to use would be highly appreciated. Thanks, Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Documentation design
I like your proposal. Few notes below. On Sun, 05 Jul 2009 23:45:31 -0400, Isaac Dupree wrote: My dream situation: both haddock-pages and hscolour-pages would be super-hyperlinked and super-readable. For example, haddock would list all a module's definitions, not just its exports. In HsColoured source, every identifier would link to its definition or the haddockumentation of its definition. and so forth. It would be so much easier to generate and browse this in HTML, than to get an IDE working, and it would be so much more readable than a mere text-editor (even with syntax hilighting) and quicker clicking on hyperlinks than grepping for everything. You do not need to resort to grep for navigation of your source code from your text editor. At least not with vim. It has tags and stack of tags. Generate tags for your source code and use Ctrl-] to navigate to the definition (or Ctrl-W} to open the definition in preview window). Any jump to definition done with Ctrl-] is stored in the stack of tags. You can return to the previous position in the stack with Ctrl-T or return to the last next position with :tag. You can check how the tag stack looks like with :tags. This way you can navigate the stack of tags comfortably and the stack of tags can correspond to the lexical (creation) stack as it would exist during execution. The only problem with this is that it works so nicely only for me currently since I have a patch applied to ghci which makes ghci to include also the non-exported symbols to the tags file. I would like to add the patch to ghci but so far there is only small support for it. If you (or anybody else) would like it drop me a note or comment on the glasgow haskell users list: http://www.haskell.org/pipermail/glasgow-haskell-users/2009- June/017399.html The :ctags improvement patch gives you a substitute for intellisense in vim. I have :inoremap ^] ^[^W}a in .vimrc so when I start to type a function name I can finish it with some completion, and (while still being in the insert mode) I can get help for it to the preview window with Ctrl-]. The ideal haddockumentation-formatting for this purpose isn't quite obvious though. For example, sometimes you want to think about a module in terms of its abstract interface, but sometimes you want to figure out how it's implemented (without reverting completely to text based code browsing). Maybe a compromise of some sort would be good. so... Here's a proposal, for a new mode (`haddock --all-internal`?, to be invoked by `cabal haddock --internal` rather than --internal's current effect of ignore-all-exports) : Files with no explicit export list can be treated as-is anyway. For all files that have an explicit export list, generate the synopsis-of-exports near the top, as usual. But have the index link, generally, to where functions are originally defined (modulo being from a non-internally-documented separate package, where it should link to the appropriate place), and have the fuller documentation below be a compilation of the identifiers *defined* in this module. I like it but some notes to the new synopsis part: You mean the index link for a symbol should go to the haddock help page not to the HsColour source page. Right? I would like some annotations aligned to the right which would indicate whether the symbol is defined locally or it is reexported. There should be also an annotation or different font to indicate whether the symbol in synopsis is exported or not (in addition to nonexported symbols being is a separate section). This is so that one can easily see what part of the help is shown. Actually that would need some revision because the sections and subsections -- *, -- **, etc. defined in the export-list in the .hs, actually are displayed 1. above the table of contents, linking to places in 2. the full list of definitions. Which might be defined in the module in a different order than they're listed in the export list. Why not add the sections into the synopsis? In this case, instead of adding them to the main doc section. But hmm... in ordinary non-internal documentation, would it be nice to *additionally* have the sections marked in the synopsis (in addition to in the Contents and in the main docs section)? Not sure I understand this part well. I assume by main document part you mean the part with detailed description and source code links. I want the contents preserved with the added last section with name Nonexported symbols, or something named like that. Adding the section names to synopsis seems like good idea to me. In such a case it could be removed from the main doc part but I would rather keep it there. But I do not really mind either way. I assume the main doc part would contain only the symbols defined in the given module (not the re-exported ones). But the synopsis part would contain the names of re-exported symbols with links to the appropriate location in the main doc part of
Re: [Haskell-cafe] Monoid wants a (++) equivalent
On Sun, 2009-07-05 at 22:30 +0200, Henning Thielemann wrote: (?) is also undefined in Prelude. Which i think is a good thing. I think it's quite nice to use (?) as an operator in higher order functions. Eg. foldr _ z [] = z foldr (?) z (x:xs) = x ? foldr (?) z xs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monoid wants a (++) equivalent
Mattias Bengtsson moonl...@dtek.chalmers.se writes: (?) is also undefined in Prelude. Which i think is a good thing. I think it's quite nice to use (?) as an operator in higher order functions. Also, it clashes with the implicit parameters extension, and combining the extension with a user-defined (?) operator resulted in (?) having a whitespace-dependent meaning, IIRC. This is perhaps not so crucial anymore, in the time since I stumbled into this -fglasgow-exts has largely been replaced by more fine-grained mechanisms, and implicit parameters has become less fashionable. -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
[Haskell-cafe] Re: Haskell Platform 2009.2.0.1 and GLUT32.DLL on Windows: which version?
Hi Peter, Peter Verswyvelen bugfact at gmail.com writes: I know GLUT32.DLL is not bundled with the Haskell Platform installer, but which GLUT32.DLL should I use? I compiled a basic example [1] successfully using the DLL downloaded from [2]. But since that's the first hit in Google, you've probably already tried it. Did you put the DLL where GHC can find it? Use $WINDIR\System32 or $WINDIR\SysWOW64 if you're on 64 bit. [1] http://netsuperbrain.com/blog/wp-content/uploads/2008/11/teapots.hs [2] http://www.xmission.com/~nate/glut.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: bloxorz clone
Very nice! Just to give feedback: It installs and works perfectly on windows. kind regards, daniel Patai Gergely schrieb: Hello all, This post is not about my own creation, it's just a little fun program written by a student of mine. You can install the bloxorz package to try it out, and read more about its background on my blog: http://just-bottom.blogspot.com/2009/07/playing-and-learning.html Gergely ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] simple state monad exercises? (besides labeling trees)
Can someone give some simple common scenarios where the state monad is useful, besides labeling trees? References to puzzles like those in project Euler or similar would be nice. Thanks! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: bloxorz clone
patai_gergely: Here's a video of bloxorz at work, very cool! http://archhaskell.wordpress.com/2009/07/04/bloxorz-an-opengl-logic-game-written-in-haskell/ I see it wasn't rehearsed in advance. ;) Will the darcs (or.. ) repository for the code be made public? I'm sure there are people in the community who'd like to contribute new levels, etc. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Haskell Platform 2009.2.0.1 and GLUT32.DLL on Windows: which version?
Okay, thanks for this feedback. I tried [2] but that failed. Since it works on your system I'll double check again tomorrow, it must be picking an incorrect GLUT32.dll I guess On Mon, Jul 6, 2009 at 5:11 PM, Mikhail Glushenkov the.dead.shall.r...@gmail.com wrote: Hi Peter, Peter Verswyvelen bugfact at gmail.com writes: I know GLUT32.DLL is not bundled with the Haskell Platform installer, but which GLUT32.DLL should I use? I compiled a basic example [1] successfully using the DLL downloaded from [2]. But since that's the first hit in Google, you've probably already tried it. Did you put the DLL where GHC can find it? Use $WINDIR\System32 or $WINDIR\SysWOW64 if you're on 64 bit. [1] http://netsuperbrain.com/blog/wp-content/uploads/2008/11/teapots.hs [2] http://www.xmission.com/~nate/glut.html ___ 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] simple state monad exercises? (besides labeling trees)
I used the State monad to implement a Brainfuck [1] interpreter a few months ago. It stored the program counter, pointer and the memory of the machine. There might have been a different (better?) way, but as I was trying to learn more about monads, it was an obvious choice. Thomas [1] http://www.muppetlabs.com/~breadbox/bf/ On Mon, Jul 6, 2009 at 18:54, Thomas Hartmantphya...@gmail.com wrote: Can someone give some simple common scenarios where the state monad is useful, besides labeling trees? References to puzzles like those in project Euler or similar would be nice. Thanks! ___ 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] ANN: bloxorz clone
Will the darcs (or.. ) repository for the code be made public? I'm sure there are people in the community who'd like to contribute new levels, etc. I don't think there is a repository at all, and I'm not even sure if Viktor wants to maintain it. I'll ask and direct him to the list. Gergely -- http://www.fastmail.fm - Or how I learned to stop worrying and love email again ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] simple state monad exercises? (besides labeling trees)
Can someone give some simple common scenarios where the state monad is useful, besides labeling trees? Emulating the VM given in this years ICFP programming contest was also a good application of the state monad. Of course you interprate much simpler language imperative languages, too. (However that might feel a bit forced as an exercise.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] excercise - a completely lazy sorting algorithm
Hi all, about a month ago, we were discussing sorting in Haskell with a friend. We realized a nice property of lazy merge-sort (which is AFAIK the implementation of Data.List.sort): Getting the first element of the sorted list actually requires O(n) time, not O(n * log n) as in imperative languages. And immediately we asked: Would it be possible to create a lazy selection/sorting algorithm so that getting any element of the sorted list/array by its index would require just O(n) time, and getting all the elements would still be in O(n * log n)? More precisely: The result of sorting an n-element list or array should be a structure that allows to ask i-th element of the result (for example, a lazy array). Asking k arbitrary elements should take no more than O(min(n * log n, k * n)) I believe that this could be done, but so far I wasn't able to implement and show it myself. I think the solution would be somewhat modified lazy quicksort (or Median of Medians algorithm if we want to be sure that we get good pivots). Perhaps somebody else would also like to give it a try? Or perhaps explain me why it's not possible? Best regards, Petr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] excercise - a completely lazy sorting algorithm
Interesting problem. I have been toying with the same problem for some time. To solve the problem in theory, I'd concentrate on getting the number of comparisons into the required O(n) resp. O(n log n) ranges. Afterwards we can think about building the infrastructure to keep the number of all operations (book keeping..) in those bounds, too. Anyway, I'll give a solution to the problem using a randomized quicksort, soon. Later we can replace the randomized pivote-picking with a deteministic linear-median algorithm. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell Platform on Ubuntu
Is there anyone working on a Haskell Platform package for Ubuntu? GHC in Ubuntu is a pain! Regards Rafael Gustavo da Cunha Pereira Pinto ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] excercise - a completely lazy sorting algorithm
On Mon, Jul 6, 2009 at 12:26 PM, Petr Pudlakd...@pudlak.name wrote:
More precisely: The result of sorting an n-element list or array should be a
structure that allows to ask i-th element of the result (for example, a lazy
array). Asking k arbitrary elements should take no more than
O(min(n * log n, k * n))
I'd argue this is not really a true use of laziness and more just
amortized cost. That said, yes, it can be done!
I'm going to use an imperative data structure because I hate you
all/sarcasm and it makes the analysis/presentation slightly easier.
To wit, we have a sorted array of unsorted bags of inputs. For
example, (suppose we start with an array of numbers 1..10, scrambled),
we might start with:
(10,{1,5,6,8,3,4,2,7,9,10})
And after some operations, it might look like:
(3,{1,3,2});(4,{6,7,5,4});(3:{8,9,10})
And we're trying to (eventually) hit the state:
(1,{1});(2,{2});...etc.
(It's not hard to see how to in constant time maintain an array of
pointers into these bags to allow finding elements.)
Now, using a linear-time selection algorithm like median-of-medians or
Chazelle's, it's easy to see how to find the k-th largest element in
such a data structure: find the bag containing the k-th element, apply
the selection algorithm. Furthermore, still in linear time, we can
(while we're working) split the bag around that element we found. So,
given the data state:
(10,{1,5,6,8,3,4,2,7,9,10})
if we're asked for the 4th largest element, we'll update to:
(3,{1,3,2});(1,{4});(6,{5,6,8,7,9,10})
So far so good, right? Now we just apply one more change: after each
lookup, we walk across the list of bags, and split each in half (as if
we were asked for the median element of each bag.) In my running
example, we'd go to:
(1,{1});{1,{2});(1,{3});(1,{4});(2,{5,6});(1,{7});(3,{8,9,10})
This is still linear time--we run a linear-time algorithm on disjoint
subsets of the input. Now, note: after k lookups to this structure,
the largest bag is at most n/2^k elements long! Couple with a slight
optimization that overwrites the lookup table into the bags with just
the correct results once the bags are small enough, and this matches
your time bounds quite nicely.
Now, I doubt it'll be fast, but that's not what you asked. Plus, come
up with a persuasive use case for a system where you /really need/ the
4th, 27th, and 957th largest elements /now/ and none of the rest, and
I promise I'll make something practically efficient. :)
If someone can translate my algorithm into a non-side-effecting one,
I'd appreciate it, but I think that like disjoint set/union, this is
probably inherently side-effecting. Yes, yes, we could use functional
arrays, but short of that I don't see a way to avoid side effects to
take care of my amortized work.
AHH
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] excercise - a completely lazy sorting algorithm
If someone can translate my algorithm into a non-side-effecting one, I'd appreciate it, but I think that like disjoint set/union, this is probably inherently side-effecting. Yes, yes, we could use functional arrays, but short of that I don't see a way to avoid side effects to take care of my amortized work. I am just working on a side-effect-free version. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] excercise - a completely lazy sorting algorithm
Hi Petr, Maybe this will give inspiration http://en.wikipedia.org/wiki/Selection_algorithm It seems to me, that you just need a selection algorithm which works in O(n * k) time for k arbitrary elements. If you combine O(n*k) selection algorithm with any O(n * lg n) sort, you furfil your time constrain. Regards, Mads Hi all, about a month ago, we were discussing sorting in Haskell with a friend. We realized a nice property of lazy merge-sort (which is AFAIK the implementation of Data.List.sort): Getting the first element of the sorted list actually requires O(n) time, not O(n * log n) as in imperative languages. And immediately we asked: Would it be possible to create a lazy selection/sorting algorithm so that getting any element of the sorted list/array by its index would require just O(n) time, and getting all the elements would still be in O(n * log n)? More precisely: The result of sorting an n-element list or array should be a structure that allows to ask i-th element of the result (for example, a lazy array). Asking k arbitrary elements should take no more than O(min(n * log n, k * n)) I believe that this could be done, but so far I wasn't able to implement and show it myself. I think the solution would be somewhat modified lazy quicksort (or Median of Medians algorithm if we want to be sure that we get good pivots). Perhaps somebody else would also like to give it a try? Or perhaps explain me why it's not possible? Best regards, Petr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe 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] Haskell Platform on Ubuntu
RafaelGCPP.Linux: Is there anyone working on a Haskell Platform package for Ubuntu? GHC in Ubuntu is a pain! The Debian team is working on packaging, but until then (or if someone on Ubuntu steps up), you'll need to use the Unix tarball: http://hackage.haskell.org/platform/2009.2.0.1/haskell-platform-2009.2.0.1.tar.gz -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Platform on Ubuntu
Rafael Gustavo da Cunha Pereira Pinto wrote: Is there anyone working on a Haskell Platform package for Ubuntu? For Haskell on Ubuntu, the vast majority of all the work is done by the Debian Haskell maintainers. Ubuntu simply takes that work and rolls packages for Ubuntu. GHC in Ubuntu is a pain! The same is also currently true for GHC on Debian stable and testing. Debian unstable is also a bit broken. However, if you know a bit about build Debian packages the Debian way then it is possible to use the Debian unstable sources on Ubuntu 8.04 and later. I've been meaning to blog this for some time :-). 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] Haskell Platform on Ubuntu
Thanks. I may even be the one to step up, if nothing happens till 9.10... I really miss up-to-date ghc in Ubuntu. 2009/7/6 Don Stewart d...@galois.com RafaelGCPP.Linux: Is there anyone working on a Haskell Platform package for Ubuntu? GHC in Ubuntu is a pain! The Debian team is working on packaging, but until then (or if someone on Ubuntu steps up), you'll need to use the Unix tarball: http://hackage.haskell.org/platform/2009.2.0.1/haskell-platform-2009.2.0.1.tar.gz -- Don -- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Platform on Ubuntu
Hello, I have uploaded the ghc package to my ppa: https://launchpad.net/~someone561/+archive/ppa But I don't work on it. I simple backport the debian sid packages. Also there are not the haskell libraries as debs. Maybe this helps you. Stefan Rafael Gustavo da Cunha Pereira Pinto wrote: Thanks. I may even be the one to step up, if nothing happens till 9.10... I really miss up-to-date ghc in Ubuntu. 2009/7/6 Don Stewart d...@galois.com mailto:d...@galois.com RafaelGCPP.Linux: Is there anyone working on a Haskell Platform package for Ubuntu? GHC in Ubuntu is a pain! The Debian team is working on packaging, but until then (or if someone on Ubuntu steps up), you'll need to use the Unix tarball: http://hackage.haskell.org/platform/2009.2.0.1/haskell-platform-2009.2.0.1.tar.gz -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] LINQ, SQL and hs-dotnet
Hi all, is there anyone who has already tried using LINQ2SQL with hs-dotnet and would care to share the experience? I'm trying to figure out what exactly it would take to access an SQL database via LINQ / hs-dotnet. Ie. whether or not it's necessary to create Entity classes, or if one can just use LINQ to generate SQL. Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] excercise - a completely lazy sorting algorithm
It seems to me, that you just need a selection algorithm which works in O(n * k) time for k arbitrary elements. If you combine O(n*k) selection algorithm with any O(n * lg n) sort, you furfil your time constrain. I guess, we also want the list to be sorted in O(1) after having selected every element. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] simple state monad exercises? (besides labeling trees)
Off the top of my head state is important when getting from A to B depends on the path you took. As such a common scenario I find myself in all the time is not having a good CLI craps game. (And which I resolve by rewriting in every language I learn.) Stake, current bet, bets outstanding, point. Lots of state. Also user interaction, varying output, error conditions, etc. depending on how complex you want. A much simpler problem is to model some large number of throws using different play strategies. Removes all the icky user interaction. Alternately you can just abuse toy problems. import Control.Monad.State fac n = execState (facs n) 1 facs n = do y - get if n == 0 then return y else do put (y*n) facs (n-1) Enjoy, -ljr Thomas Hartman wrote: Can someone give some simple common scenarios where the state monad is useful, besides labeling trees? References to puzzles like those in project Euler or similar would be nice. Thanks! ___ 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] excercise - a completely lazy sorting algorithm
On Mon, Jul 6, 2009 at 4:32 PM, Matthias Görgensmatthias.goerg...@googlemail.com wrote: It seems to me, that you just need a selection algorithm which works in O(n * k) time for k arbitrary elements. If you combine O(n*k) selection algorithm with any O(n * lg n) sort, you furfil your time constrain. I guess, we also want the list to be sorted in O(1) after having selected every element. I think he's suggesting something along the lines of: for the first \log n requests, use a selection. On the \log n + 1th request, just sort the whole thing. This obviously isn't the spirit of what's wanted, but does in fact meet the time bounds. AHH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Catering for similar operations with and without state
Well, the simplest solution I can think of is below. The OtherNormalStateT doesn't actually have any state at all, but still gets state from the StateT 'below' it and returns a result. This is still a bit ugly, but it compiles - and although I haven't tested it properly yet, simply implementing the 'other' helper function to do the work should be fine. It's a question of how smart the compiler is. Obviously this is inefficient in theory, but will the compiler notice we are passing around a 'unit' state and that the s - (a,s) function doesn't care about the input perhaps. I'd expect the overhead from this to be fairly small and it does allow me to continue using the same paradigm for stateless versions of my normal generator. I have seen people do similar things when they wish to carry around state but have no result, and thus the result is set to (). I can't see why this is any less inefficient than that? type BoxMullerStateT = StateT (Maybe Double) type BoxMullerRandomStateStack = BoxMullerStateT MyRngState instance NormalClass BoxMullerRandomStateStack where generateNormal = StateT $ \s - case s of Just d - return (d,Nothing) Nothing - do qrnBaseList - nextRand let (norm1,norm2) = boxMuller (head qrnBaseList) (head $ tail qrnBaseList) return (norm1,Just norm2) -- New stateless StateT below! type OtherNormalStateT = StateT () type OtherRandomStateStack = OtherNormalStateT MyRngState instance NormalClass OtherRandomStateStack where generateNormal = StateT $ \_ - do rn:rns - nextRand return ( other rn, () ) On 17 Jun 2009, at 07:38, Jason Dagit wrote: Hi Phil, On Mon, Jun 15, 2009 at 5:23 PM, Phil p...@beadling.co.uk wrote: Hi, I'm trying to think around a problem which is causing me some difficulty in Haskell. I'm representing a stateful computation using a State Transform - which works fine. Problem is in order to add flexibility to my program I want to performs the snip g my own Monad from scratch but this crossed my mind as another possibillity - i.e. a Monad that either has a state of maybe double, or has no state at all? I have a feeling I'd just 'return' the pure computations into the state monad. My example code above seems weird and heavy weight to me. I'd love to see what you figure you. Jason ___ 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] excercise - a completely lazy sorting algorithm
The sorted array of bags of unsorted input is a nice idea. However,
you have to use the data structure in a single-threaded [1] fashion to
obtain the claimed bounds.
Here's a pure solution that uses amortization and laziness.
import qualified Data.Sequence as S
import Data.Sequence (())
import Data.Foldable
import Data.Monoid
Suppose we have a function to find the the median of a list, and
partition it into three sublists: Smaller than the median, equal to
the media, larger than the median. That function should run in linear
time.
partitionOnMedian :: forall a. (Ord a) = (S.Seq a) - BTreeRaw a (S.Seq a)
where the following data structure holds the sublists and some
bookkeeping information:
data BTreeRaw a m = Leaf
| Node {cmp::(a-Ordering)
, lN :: Int
, less::m
, eq :: (S.Seq a)
, gN :: Int
, greater::m
}
where 'lN' and 'gN' are the length of 'less' and 'greater'.
We can make BTreeRaw a functor:
instance Functor (BTreeRaw a) where
fmap f Leaf = Leaf
fmap f (Node c lN l e gN g) = Node c lN (f l) e gN (f g)
Now using a fixed-point construction we can bootstrap a sorting
algorithm from partitionOnMedian:
data Fix m = Fix {unfix :: (m (Fix m))}
type BTree a = Fix (BTreeRaw a)
treeSort :: forall a. (Ord a) = S.Seq a - BTree a
treeSort = Fix . helper . partitionOnMedian
where helper = fmap (Fix . helper . partitionOnMedian)
Now treeSort produces the thunk of a balanced binary search tree. Of
course we can get a sorted list out of it (forcing the whole
structure):
flatten :: BTree a - S.Seq a
flatten (Fix Leaf) = S.empty
flatten (Fix (Node _ lN l e gN g)) = flatten l e flatten g
mySort = flatten . treeSort
But we can also get elements efficently, forcing only a linear amount
of comparisions in the worst case:
index :: BTree a - Int - a
index (Fix Leaf) _ = error tried to get an element of Leaf
index (Fix (Node lN l e gN g)) i | i lN
= index l i
| i - lN S.length e
= S.index e (i-lN)
| i - lN - S.length e gN
= index g (i - lN - S.length e)
| i - lN - S.length e - gN = 0
= error index out of bounds
Although we do have to force comparisions only once every time we
touch the same element in the tree, we do still have to traverse the
tree (in logarithmic time).
If you want linear time access on first touch of an element and
constant time access afterwards us toArray:
toArray :: (IA.IArray a t) = Fix (BTreeRaw t) - a Int t
toArray tree = IA.listArray (0,maxI) (map (index tree) [0..maxI])
where size (Fix Leaf) = 0
size (Fix (Node lN _ e gN _)) = lN + S.length e + gN
maxI = size tree - 1
[1] Single-Threaded in the sense of Okasaki's use of the word.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Implementing Las Vegas algorithms in Haskell
A Las Vegas algorithm, like randomized quicksort, uses a source of randomness to make certain decisions. However its output is unaffected by the randomness. So a function f :: RandomGen g = g - a - b implementing a Las-Vegas-Algorithm 'looks' like a pure function, ignoring its first argument and depending solely on its second argument. What is an idiomatic way to implement such a function? I believe, Monads are too linear and strict. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: what about moving the record system to an addendum?
Well, without a replacement, it seems odd to remove it. Also, Haskell currently doesn't _have_ a record syntax (I think it was always a misnomer to call it that) it has 'labeled fields'. None of the proposed record syntaxes fit the same niche as labeled fields so I don't see them going away even if a record syntax is added to haskell in the future. I would like to see the simple modifications to the record syntax listed on this page though http://hackage.haskell.org/trac/haskell-prime/wiki/ExistingRecords and a reworking of the standard to not refer to the current system as a 'record syntax' but rather a 'labeled fields' syntax. 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] Re: Could FFI support pass-by-value of structs?
On Thu, Jul 02, 2009 at 03:01:48AM +0400, Bulat Ziganshin wrote: Hello Duncan, Thursday, July 2, 2009, 2:57:29 AM, you wrote: You don't need it to be the same between Windows and Unix, it just has to be standard on each platform, which it is. There are really only two ABIs in common use on x86, the System V ABI and the MS one (which apart from the stdcall calling convention only differs in the bitfield layout iirc). you mean that on windows gcc, msvc and all other C compilers use the same ABI for passing and packing structs? Yes. If you think about it, otherwise it would be impossible to interface with system provided shared libraries (like libc) unless there is a standard. It sometimes varies across different OS's, but for any OS/chip combo there is a single defined C ABI. It is generally called the 'system V' ABI for historical reasons, even though chances are people arn't using it for system V. Usually it is provided by the chip manufacturer and all OS's follow it. Unless they feel like being a PITA, but in that case they have their own standards document that gcc will follow as an option. So, yes. there is always _some_ well defined ABI for the C langauge on a given platform. 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] golf, predicate check function for MonadPlus (was Re: How to read safely?)
On Thursday 02 July 2009 6:36:09 am Jon Fairbairn wrote: check :: (MonadPlus m) = (a - Bool) - a - m a check p a | p a = return a | otherwise = mzero I tried Hoogling for a function like check, but couldn't find it. Surely there's one in a library somewhere? It looks useful to me. (I'm rather taken by way the check (all isSpace . snd) part reads) Monad.guard comes close but fails to get the cigar; in fact guard b == check (const b) () So check is more general. I've often noticed the need for a similar function in conjunction with unfoldr: -- This is overly general for unfoldr, but it lines up with check stopAt :: (MonadPlus m) = (a - Bool) - (a - b) - a - m b stopAt p f x | p x = mzero | otherwise = return (f x) -- stopAt p f x = guard (not $ p x) return (f x) -- stopAt p f = liftM2 () (guard . not . p) (return . f) -- etc. Then you can write: unfoldr (stopAt p $ f) where p is a stopping predicate based on the seed, and f unfolds the seed one step. This lets you use the many functions in the standard library that have types like: s - (a, s) where unfoldr wants them to instead be: s - Maybe (a, s) However, I don't really like the name stopAt, and have never come up with anything better. And of course: check = flip stopAt id . not -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Las Vegas algorithms in Haskell
2009/7/6 Matthias Görgens matthias.goerg...@googlemail.com A Las Vegas algorithm, like randomized quicksort, uses a source of randomness to make certain decisions. However its output is unaffected by the randomness. So a function f :: RandomGen g = g - a - b implementing a Las-Vegas-Algorithm 'looks' like a pure function, ignoring its first argument and depending solely on its second argument. What is an idiomatic way to implement such a function? I believe, Monads are too linear and strict. Interesting question! Well, you could make your own random generator for the lifetime of the function, with a fixed seed. I'd say this is the most honest way to do it; however, might a malicious user discover your seed, he could design an input that would make your algorithm perform poorly. I'm wary of saying you could use unsafePerformIO . randomRIO to get a seed. But I think some sort of unsafe something has to be involved, since you are representing a very advanced proof obligation (the algorithm is independent of the randomness). Keep us (me) posted on developments on this idea. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] BostonHaskell: Next meeting - July 16th at MIT CSAIL Reading Room (32-G882)
I'm pleased to announce the July meeting of the Boston Area Haskell Users' Group. Based on the feedback from the June meeting and the constraints of our speakers, the July meeting has been scheduled for Thursday, July 16th from 6:30pm - 8:30pm. Like the June meeting, it will be held in the MIT CSAIL Reading Room (32-G882, i.e. a room on the 8th floor of the Gates Tower of the MIT's Stata Center at 32 Vassar St in Cambridge, MA). We have the following two talks scheduled: An Introduction to GHC Hacking by Alec Heller Haskell on the iPhone by Ryan Trinkle (a more in-depth discussion than his on-the-spot Lightning Talk last month). As always, there will be a break between the talks for discussion and mingling. We have openings for Lightning Talks (5-minute talk, 2-minute QA) during that period. We are also open to short, relevant advertisements (like my Hac Phi plug last month). If you're interested in giving a Lightning Talk, have an advertisement you'd like to share or are interested in speaking at a future meeting, please contact me at rav...@alum.mit.edu. I'd also appreciate it if people who can (and can't) attend this meeting fill out the attendance poll here: http://www.learnmyself.com/poll10828x74C54f13 I apologize for the URL, but Google Groups seems to ban JavaScript and I didn't want to delay this announcement while I tried to come up with something more convenient. Responding to this poll will help with two things: 1. Getting an idea of what fraction of the Boston-area Haskell community can and can't attend this meeting (to help with future scheduling). 2. Giving me an estimated count of attendees, should I manage to secure a sponsor for refreshments. Sponsorship of or other assistance with refreshments is still being eagerly solicited. If you have any questions about the meeting please send them to the BostonHaskell mailing list: bostonhask...@googlegroups.com or contact me directly. I look forward to seeing many Boston-area Haskellers at the July meeting! Thank you, - Ravi Nanavati ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Las Vegas algorithms in Haskell
2009/7/6 Matthias Görgens matthias.goerg...@googlemail.com A Las Vegas algorithm, like randomized quicksort, uses a source of randomness to make certain decisions. However its output is unaffected by the randomness. So a function f :: RandomGen g = g - a - b implementing a Las-Vegas-Algorithm 'looks' like a pure function, ignoring its first argument and depending solely on its second argument. What is an idiomatic way to implement such a function? I believe, Monads are too linear and strict. I believe this would be a good place to apply implicit configurations. http://okmij.org/ftp/Haskell/types.html#Prepose Let me know if it solves your problem. What I recall of the paper is that it should work nicely for your situation. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] golf, predicate check function for MonadPlus (was Re: How to read safely?)
On Mon, Jul 6, 2009 at 8:49 PM, Dan Doeldan.d...@gmail.com wrote: I've often noticed the need for a similar function in conjunction with unfoldr: -- This is overly general for unfoldr, but it lines up with check stopAt :: (MonadPlus m) = (a - Bool) - (a - b) - a - m b stopAt p f x | p x = mzero | otherwise = return (f x) -- stopAt p f x = guard (not $ p x) return (f x) -- stopAt p f = liftM2 () (guard . not . p) (return . f) -- etc. Then you can write: unfoldr (stopAt p $ f) I have the following function sitting around: unfoldUntil :: (b - Bool) - (b - (a, b)) - b - [a] unfoldUntil p f n = unfoldr g n where g m | p m = Nothing | otherwise = Just $ f m But I don't remeber where I picked it up from. It looks like it fills a similar niche. Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
