News aggregator

Proposal: parametrize tree stem container type in containers

libraries list - Thu, 03/19/2015 - 10:31pm
A few years ago I uploaded the package generic-tree to Hackage (before I knew the customary version scheme, sorry about that) which has trees parametrized over stem container type: data Tree v a = Node a (v (Tree v a)) As this is a functional superset of the containers tree, I think it appropriate to include in containers, which I hereby propose. Ultimately, if this is accepted, I would like to define the list-specialized tree in terms of this.
Categories: Offsite Discussion

First order pattern matching.

Haskell on Reddit - Thu, 03/19/2015 - 7:59pm

Title edit: not first order, first class*

Is there any language extension that enables first-class pattern matching? For example:

((a,b) => a+b) (1,2) == 3 (x:xs => xs) [1,2,3] == [2,3]

In general,

(pattern => match)

Equates to

(\ x -> let pattern = x in match) submitted by Hadkell
[link] [11 comments]
Categories: Incoming News

Staggered zip, or fold with 2 elements at a time

Haskell on Reddit - Thu, 03/19/2015 - 7:34pm

If there is a better location to post this question, please let me know.

Suppose given

1. A finite list x = [x^1, x^2 .. x^n] 2. A pure binary function h, and pure unary functions f and g.

It is pretty easy to apply the functions to every element of x, with higher-order functions instead of recursion:

aligned1 f g h x = (h <$> f <*> g) `map` x aligned2 f g h x = (\p -> h (f p) (g p)) `map` x

Here, x is traversed one element at a time and the fused functions are applied to produce an element of the result. Sequential evaluation is not needed because each element of the result only depends on one element of x. Also, the higher-order function takes care of the raw recursion.

Is there a way to achieve the same for the following?

y^1 = f x^1 y^(n+1) = g x^n y^i = h ( f x^i ) ( g x^(i-1) )

For example, if h = (+) and f,g :: a -> Int, the job would get done with:

staggered1 f g x = zipWith (+) ((map f x) ++ [0]) (0 : map g x)

This code zips the following two lists with addition (+):

[ f x^1 , f x^2 .. f x^n , 0 ] [ 0 , g x^1 .. g x^(n-1) , g x^n ]

Alternatively, one could map f and g on x, and then use raw recursion to zip the two lists:

staggered2 f g h x = y : inner ys zs where y:ys = map f x zs = map g x inner [] (q:qs) = q : inner [] qs inner (p:ps) (q:qs) = h p q : inner ps qs inner _ _ = []

Or, an accumulator variable could be used to store the previous x or (f x):

staggered3a f g h (x:xs) = (f x) : inner x xs where inner acc [] = g acc : [] inner acc (y:ys) = h (f y) (g acc) : inner y ys staggered3b f g h (x:xs) = f x : inner (g x) xs where inner acc [] = acc : [] inner acc (y:ys) = h (f y) acc : inner (g y) ys

More generally, this accumulator could even be a queue to store several consecutive elements at once...

Is there an elegant way to zip staggered maps on the same list, or fold consecutive elements at a time? The goal is to traverse x only once, avoid raw recursion with higher order functions, preserve the local dependence on consecutive elements of x, and avoid forcing sequential execution.

Are there existing libraries that do this? Maybe a generalization of this concept?

BONUS (pat on the back) for applicative style.

PS. In my context, (f xi ) is the remainder from applying (g xi ), and vice versa. So, in theory, they could be calculated at the same time. I haven't found a way to do this yet, but that's a whole other question :)

submitted by newestHaskeller
[link] [20 comments]
Categories: Incoming News

Mark Jason Dominus: Rectangles with equal area and perimeter

Planet Haskell - Thu, 03/19/2015 - 6:00pm

Wednesday while my 10-year-old daughter Katara was doing her math homework, she observed with pleasure that a rectangle has a perimeter of 18 units and also an area of 18 square units. I mentioned that there was an infinite family of such rectangles, and, after a small amount of tinkering, that the only other such rectangle with integer sides is a square, so in a sense she had found the single interesting example. She was very interested in how I knew this, and I promised to show her how to figure it out once she finished her homework. She didn't finish before bedtime, so we came back to it the following evening.

This is just one of many examples of how she has way too much homework, and how it interferes with her education.

She had already remarked that she knew how to write an equation expressing the condition she wanted, so I asked her to do that; she wrote $$(L×W) = ([L+W]×2).$$ I remember being her age and using all different shapes of parentheses too. I suggested that she should solve the equation for , getting on one side and a bunch of stuff involving on the other, but she wasn't sure how to do it, so I offered suggestions while she moved the symbols around, eventually obtaining $$W = 2L\div (L-2).$$ I would have written it as a fraction, but getting the right answer is important, and using the same notation I would use is much less so, so I didn't say anything.

I asked her to plug in and observe that popped right out, and then similarly that yields , and then I asked her to try the other example she knew. Then I suggested that she see what did: it gives , This was new, so she checked it by calculating the area and the perimeter, both . She was very excited by this time. As I have mentioned earlier, algebra is magical in its ability to mechanically yield answers to all sorts of questions. Even after thirty years I find it astonishing and delightful. You set up the equations, push the symbols around, and all sorts of stuff pops out like magic. Calculus is somehow much less astonishing; the machinery is all explicit. But how does algebra work? I've been thinking about this on and off for a long time and I'm still not sure.

At that point I took over because I didn't think I would be able to guide her through the next part of the problem without a demonstration; I wanted to graph the function and she does not have much experience with that. She put in the five points we already knew, which already lie on a nice little curve, and then she asked an incisive question: does it level off, or does it keep going down, or what? We discussed what happens when gets close to 2; then shoots up to infinity. And when gets big, say a million, you can see from the algebra that is a hair more than 2. So I drew in the asymptotes on the hyperbola.

Katara is not yet familiar with hyperbolas. (She has known about parabolas since she was tiny. I have a very fond memory of visiting Portland with her when she was almost two, and we entered Holladay park, which has fountains that squirt out of the ground. Seeing the water arching up before her, she cried delightedly “parabolas!”)


Once you know how the graph behaves, it is a simple matter to see that there are no integer solutions other than and . We know that does not work. For the value of is always strictly between and . For there is no value of that works at all. For the formula says that is negative, on the other branch of the hyperbola, which is a perfectly good numerical solution (for example, ) but makes no sense as the width of a rectangle. So it was a good lesson about how mathematical modeling sometimes introduces solutions that are wrong, and how you have to translate the solutions back to the original problem to see if they make sense.

[ Addendum 20150330: Thanks to Steve Hastings for his plot of the hyperbola, which is in the public domain. ]

Categories: Offsite Blogs

ANN: Magic Cookies! Android board game in Haskell

haskell-cafe - Thu, 03/19/2015 - 4:11pm
Dear Café This is a just a quick announcement: we have just released Magic Cookies, an Android board game written in Haskell. It is now available on Google Play [1]. The game uses the Functional Reactive Programming library Yampa and SDL2 for multimedia. If you like the game, please share the link on facebook/twitter/etc and let all of your friends know. We have gone through dozens of iterations during beta testing, but we cannot guarantee that the game works 100% perfectly on all devices. If you find a bug, or anything else you don't like, please do not rate low. Instead, open an issue [2] or send us an email (support< at >keera.co.uk). Suggestions are also welcome. We will continue working to make the game lighter, faster, and more fun. See [3] for more details, and to sign up as a beta-tester for other games we are already working on. We certainly enjoyed making it, and we hope you all enjoy playing it. All the best Ivan, Fass & Jorge [1] https://play.google.com/store/apps/details?id=uk.co.keera.game
Categories: Offsite Discussion

Noam Lewis: A simple bash script for monitoring the output of a running process

Planet Haskell - Thu, 03/19/2015 - 2:21pm

I got tired of my screen getting flooded with text when all I wanted was to see the last output line at any given time. What I really want is to just see one output line and have it replaced with some newer text when it’s available. So I wrote a script (in, ahem, bash) that lets your do exactly this. Call it “tailor.sh” or whatever you want:

(If the code below is screwed up, see it here on gist)

#!/bin/bash -eu LOG_FILE=$1 SB="stdbuf -i0 -oL" shift tput sc $@ 2>&1 \ | $SB tee $LOG_FILE \ | $SB cut -c-$(tput cols) \ | $SB sed -u 's/\(.\)/\\\1/g' \ | $SB xargs -0 -d'\n' -iyosi -n1 bash -c 'tput rc;tput el; printf "\r%s" yosi' EXIT_CODE=${PIPESTATUS[0]} tput rc;tput el;printf "\r" # Delete the last printed line exit $EXIT_CODE

I use it in a test env bringup script to run some builds. Instead of having to lose all the context of the wrapping script, I now see just a single output line of the invoked builds at any given time.


Categories: Offsite Blogs

Switched from lens-family to lens

Haskell on Reddit - Thu, 03/19/2015 - 2:06pm

The uses of it for working with JSON finally got to me.

submitted by andrewthad
[link] [comment]
Categories: Incoming News

can't STOP after interrupt winGHCi or ghci

haskell-cafe - Thu, 03/19/2015 - 8:59am
Now I realize maybe I didn't make my point clear. What I want is not just interrupting the output of the compiler, but also stop the output of the compiler after interrupting. Van: Haskell-Cafe [mailto:haskell-cafe-bounces< at >haskell.org] Namens Kees Bleijenberg Verzonden: woensdag 18 maart 2015 11:12 Aan: haskell-cafe< at >haskell.org Onderwerp: [Haskell-cafe] can't nterrupt winGHCi or ghci With a haskell program I generated a very big haskell file. Sometimes the generated haskell is not valid. If I load the genearated file in winGHCi a flood of error messages streams over the screen. If I press ctrl-break WinGHCi stops and says interrupted. If I click Ok the program continues printing error messages. Ctrl-c or just c, doesn't help. So I have to wait until WinGHCi has shown all error messages (can take minutes) or close the WinGHCi window. Ghci has (on Windows) the same behaviour. Is there a special key combination to stop Ghc or Ghci or is this a bug? Kees _______________________________________
Categories: Offsite Discussion

Incremental sequence sorting

haskell-cafe - Wed, 03/18/2015 - 10:21pm
I had an idea, and it's kind of complicated, so I was wondering if I could get a sanity check from someone before putting *too* much time into it. Specifically, I was thinking about a sort of incremental sorting of sequences (in Data.Sequence). The idea is very closely related to the incremental sorting described by Navarro and Paredes ( http://www.dcc.uchile.cl/~gnavarro/ps/algor09.pdf ). The basic concept: sequences are represented as Hinze-Paterson 2-3 finger trees. They are fairly lazy, so building them from the top down tends to be a good thing. Suppose I have a sequence to be sorted. To start building the result sequence, I need to know which elements go in the first digit and which go in the last digit. To do this, I need two order statistics, starting with one separating the first digit from the rest, then one separating the last digit from the rest. Once I have separated these, I can produce the top of the sequence. The digit separation is the same all down the spine. Within digits, 2-3 trees split
Categories: Offsite Discussion

Proposed significant breaking changes to Win32

haskell-cafe - Wed, 03/18/2015 - 8:24pm
There are some discussions going on in this GitHub issue: https://github.com/haskell/win32/issues/24 with proposals for extensive breaking changes to the Win32 library. Well over 100 functions would be involved. These changes would finally fix many long outstanding defects in the API, some of which make it difficult to use important Win32 functions in the way originally intended. It is estimated that about 70 packages on Hackage depend on Win32 and could potentially be affected. If you might be affected, have an opinion, or just are interested, please drop by the GitHub issue. There is also a thread on the libraries mailing list. Thanks, Yitz
Categories: Offsite Discussion