News aggregator

There was an interesting question by ‘Fool’ recently on the StackExchange site for Boardgames: How do you play a game like Rock-Paper-Scissors with friends online? Or any other game where players have to simultaneously submit their moves (e.g. Diplomacy, or Rock-Paper-Scissors-Lizzard-Spock), which, as I just learned, are simultaneous action selection games. While there are websites dedicated to playing specific games, such as webdiplomacy.net, we could not find a generic one that you can use if you, for example, invent your own variants of a game.

So I created one: At you-say-first.nomeata.de you can enter rooms and share the URL with your friends. On the one hand, you have a regular chat room there. But there is also the possibility to enter moves (whatever a move may be to you) and only when all players have done that and marked the move as final, it is shown to everyone. If you want to try it out: There is an integrated, not very fancy Rock-Paper-Scissors-playing bot. Just enter a room, join and say „I want to play!“

Note that this site can be used for more than just for games. Have you ever observed that persons would often want other to express their preference (e.g. where to dine) first to not reveal their own preference, so that they can (or pretend to) change their mind if they would contradict? In such situations simultaneous action selection can be a fairer method.

A technical note: I created this web app using meteor (a JavaScript framework building on node.js and MongoDB that allows for reactive programming), and it is also hosted on meteor.com. I chose Meteor after someone mentioned Firebase to me, which looked very slick, but was not Free Software, so I looked for alternatives. I did not do any cross-browser-testing, and the UI design could be improved, so if you want to help out (or just complain), please use the GitHub code repository and issue tracker.

I'm looking for the version of haskell platform that was "supposed" to be released May 6. It seems like it isn't out yet. What's preventing this from happening, and is there anything I can do to help? Regards, - Clark _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Posted on May 11, 2013 Tags: programming, recursion, iteration, python, google code jam, puzzles, recursion-to-iteration series

Alternative title: I wish Python had tail-call elimination.

Recursive programming is the cat’s meow because it maps so easily to proof by induction, making it easy to design algorithms and prove them correct. Getting stuff right is what programming is all about.

But recursion is poorly supported by many popular programming languages. Drop a large input into a recursive algorithm in Python, and you’ll probably hit the runtime’s recursion limit. Raise the limit, and you may run out of stack space and segfault.

These are not happy outcomes.

Therefore, an important trick of the trade is knowing how to translate recursive algorithms into iterative algorithms. That way, you can design, prove, and initially code your algorithms in the almighty realm of recursion. Then, after you’ve got things just the way you want them, you can translate your algorithms into equivalent iterative forms through a series of mechanical steps. You can prove your cake and run it in Python, too.

This topic – turning recursion into iteration – is fascinating enough that I’m going to do a series of posts on it. Tail calls, trampolines, continuation-passing style – and more. Lots of good stuff.

For today, though, let’s just look at one simple method and one supporting trick.

The Simple Method

This translation method works on many simple recursive functions. When it works, it works well, and the results are lean and fast. I generally try it first and consider more complicated methods only when it fails.

In a nutshell:

1. Study the function.
2. Convert all recursive calls into tail calls. (If you can’t, stop. Try another method.)
3. Introduce a one-shot loop around the function body.
4. Convert tail calls into continue statements.
5. Tidy up.

An important property of this method is that it’s incrementally correct – after every step you have a function that’s equivalent to the original. So if you have unit tests, you can run them after each and every step to make sure you didn’t make a mistake.

Let’s see the method in action.

Example: factorial

With a function this simple, we could probably go straight to the iterative version without using any techniques, just a little noggin power. But the point here is to develop a mechanical process that we can trust when our functions aren’t so simple or our noggins aren’t so powered. So we’re going to work on a really simple function so that we can focus on the process.

Ready? Then let’s show these guys how cyber-commandos get it done! Mark IV style!

1. Study the original function.

   def factorial(n): if n < 2: return 1 return n * factorial(n - 1)

   Nothing scary here. Just one recursive call. We can do this!

2. Convert recursive calls into tail calls.

   def factorial1a(n, acc=1): if n < 2: return 1 * acc return factorial1a(n - 1, acc * n)

   (If this step seemed confusing, see the Bonus Explainer at the end of the article for the “secret feature” trick behind the step.)

3. Introduce a one-shot loop around the function body. You want while True: body ; break.

   def factorial1b(n, acc=1): while True: if n < 2: return 1 * acc return factorial1a(n - 1, acc * n) break

   Yes, I know putting a break after a return is crazy, but do it anyway. Clean-up comes later. For now, we’re going by the numbers.

4. Replace all recursive tail calls f(x=x1, y=y1, ...) with (x, y, ...) = (x1, y1, ...); continue. Be sure to update all arguments in the assignment.

   def factorial1c(n, acc=1): while True: if n < 2: return 1 * acc (n, acc) = (n - 1, acc * n) continue break

   For this step, I copy the original function’s argument list, parentheses and all, and paste it over the return keyword. Less chance to screw something up that way. It’s all about being mechanical.

5. Tidy the code and make it more idiomatic.

   def factorial1d(n, acc=1): while n > 1: (n, acc) = (n - 1, acc * n) return acc

   Okay. This step is less about mechanics and more about style. Eliminate the cruft. Simplify. Make it sparkle.

6. Wait. That’s it. You’re finished!

What have we gained?

We just did five steps of work to convert our original, recursive factorial function into the equivalent, iterative factorial1d function. If our programming language had supported tail-call elimination, we could have stopped at step two with factorial1a. But nooooooo… We had to press on, all the way through step five, because we’re using Python. It’s almost enough to make a cyber-commando punch a kitten.

No, the work wasn’t hard, but it was still work. So what did it buy us?

Too see what it bought us, let’s look inside the Python run-time environment. We’ll use the Online Python Tutor’s visualizer to observe the build-up of stack frames as factorial, factorial1a, and factorial1d each compute the factorial of 5.

This is very cool, so don’t miss the link: Visualize It! (ProTip: Open it in a new tab.)

Click the “Forward” button to step through the execution of the functions. Notice what happens in the Frames column. When factorial is computing the factorial of 5, five frames build up on the stack. Not a coincidence.

Same thing for our tail-recursive factorial1a. (You’re right. It is tragic.)

But not for our iterative wonder factorial1d. It uses just one stack frame, over and over, until it’s done. That’s economy!

That’s why we did the work. Economy. We converted O(n) stack use into O(1) stack use. When n could be large, that savings matters. It could be difference between getting an answer and getting a segfault.

Not-so-simple cases

Okay, so we tackled factorial. But that was an easy one. What if your function isn’t so easy? Then it’s time for more advanced methods.

That’s our topic for next time.

Until then, keep your brain recursive and your Python code iterative.

Bonus Explainer: Using secret features for tail-call conversion

In step 2 of The Simple Method, we converted the recursive call in this code:

def factorial(n): if n < 2: return 1 return n * factorial(n - 1) # <-- right here!

into the recursive tail call in this code:

def factorial(n, acc=1): if n < 2: return 1 * acc return factorial(n - 1, acc * n) # <-- oh, yeah!

This conversion is easy once you get the hang of it, but the first few times you see it, it seems like magic. So let’s take this one step by step.

First, the problem. We want to get rid of the n * in the following code:

return n * factorial(n - 1)

That n * stands between our recursive call to factorial and the return keyword. In other words, the code is actually equivalent to the following:

x = factorial(n - 1) result = n * x return result

That is, our code has to call the factorial function, await its result (x), and then do something with that result (multiply it by n) before it can return its result. It’s that pesky intermediate doing something we must get rid of. We want nothing but the recursive call to factorial in the return statement.

So how do we get rid of that multiplication?

Here’s the trick. We extend our function with a multiplication feature and use it to do the multiplication for us.

Shh! It’s a secret feature, though, just for us. Nobody else.

In essence, every call to our extended function will not only compute a factorial but also (secretly) multiply that factorial by whatever extra value we give it. The variables that hold these extra values are often called “accumulators,” so I use the name acc here as a nod to tradition.

So here’s our function, freshly extended:

def factorial(n, acc=1): if n < 2: return acc * 1 return acc * n * factorial(n - 1)

See what I did to add the secret multiplication feature? Two things.

First, I took the original function and added an additional argument acc, the multiplier. Note that it defaults to 1 so that it has no effect until we give it some other value (since 1⋅x=x). Gotta keep the secret secret, after all.

Second, I changed every single return statement from return {whatever} to return acc * {whatever}. Whenever our function would have returned x, it now returns acc * x. And that’s it. Our secret feature is done! And it’s trivial to prove correct. (In fact, we just did prove it correct! Re-read the second sentence.)

Both changes were entirely mechanical, hard to screw up, and, together, default to doing nothing. These are the properties you want when adding secret features to your functions.

Okay. Now we have a function that computes the factorial of n and, secretly, multiplies it by acc.

Now let’s return to that troublesome line, but in our newly extended function:

return acc * n * factorial(n - 1)

It computes the factorial of n - 1 and then multiplies it by acc * n. But wait! We don’t need to do that multiplication ourselves. Not anymore. Now we can ask our extended factorial function to do it for us, using the secret feature.

So we can rewrite the troublesome line as

return factorial(n - 1, acc * n)

And that’s a tail call!

So our tail-call version of the factorial function is this:

def factorial(n, acc=1): if n < 2: return acc * 1 return factorial(n - 1, acc * n)

And now that all our recursive calls are tail calls – there was only the one – this function is easy to convert into iterative form using The Simple Method described in the main article.

Let’s review the Secret Feature trick for making recursive calls into tail calls. By the numbers:

1. Find a recursive call that’s not a tail call.
2. Identify what work is being done between that call and its return statement.
3. Extend the function with a secret feature to do that work, as controlled by a new accumulator argument with a default value that causes it to do nothing.
4. Use the secret feature to eliminate the old work.
5. You’ve now got a tail call!
6. Repeat until all recursive calls are tail calls.

With a little practice, it becomes second nature. So…

Exercise: Get your practice on!

You mission is to get rid of the recursion in the following function. Feel like you can handle it? Then just fork the exercise repo and do your stuff to exercise1.py.

def find_val_or_next_smallest(bst, x): """Get the greatest value <= x in a binary search tree. Returns None if no such value can be found. """ if bst is None: return None elif bst.val == x: return x elif bst.val > x: return find_val_or_next_smallest(bst.left, x) else: right_best = find_val_or_next_smallest(bst.right, x) if right_best is None: return bst.val return right_best

Have fun!

Hello everybody, I'm trying to formulate the stream processing problem, which doesn't seem to be solved fully by the currently existing patterns. I'm experimenting with a new idea, but I want to make sure that I don't miss any defining features of the problem, so here is my list. A stream processing abstraction should: * have a categorically proven design (solved by iteratees, pipes), * be composable (solved by all of them), * be reasonably easy to understand and work with (solved by conduit, pipes), * support leftovers (solved by conduit and to some degree by iteratees), * be reliable in the presence of async exceptions (solved by conduit, pipes-safe), * hold on to resources only as long as necessary (solved by conduit and to some degree by pipes-safe), * ideally also allow upstream communication (solved by pipes and to some degree by conduit). * be fast (solved by all of them). Anything else you would put in that list? Greets, Ertugrul

submitted by Onlogic
[link] [8 comments]

Hi All,

I'm writing my first greenfield project in Haskell having been tinkering for quite a while. It's become apparent that I don't have a good intuition for "haskell in the large" (and this is a feeling I've seen expressed before by people new to the language). If it's OK I'd like to ask some general big picture haskell application design questions here in the hope that they will help myself and others.

Here's what I'm writing for some context:

I want to write a client library for my excellent online small business accounting package, freeagent (which is an oauth2 web service). Eventually I'd like to make it into a bridging library between freeagent and hledger. I'll need the following:

• Oauth2 library and http client. I've gone for hoauth2 and http-streams. I'm not set in stone here; any pointers?

• A library to manage a ~/.hfreeagent config file. The config file will need to manage and store the oauth credentials (id, secret, hostname etc), the location of ledger files, and token management (oauth2 tokens need to be periodically refreshed). ConfigFile or bos' library look like good options here.

• A rest client which marshals json objects to haskell and thence to however hledger represents things. Aeson looks good for this one.

So far so good!

So the questions then:

• What should my monad stack look like? The presence of the config suggests a ReaderT somewhere. But I'll also need to write to the config file when I refresh a token, so do I need StateT? Or do I need two separate interfaces? I understand monads and transformers, but I now realise that I have no idea how to design them.

• Any pointers on structuring the library (directory structure, module naming etc).

• Is there anything that could generate my types from json for me? Something like F#'s type providers, template haskell or some clever lensing. Or do I have to go and manually define all of the types in the API that I want to use: https://dev.freeagent.com/docs?

• How would you model the workflow of looking up the token, checking if it's still valid, refreshing it if not and then making it available to the rest client? (this goes back to the monad question I guess).

I think that will do for now. The library will be open source https://github.com/perurbis/hfreeagent, and I'd like for it to serve as a roadmap if possible for folks moving from playing with and liking Haskell to actually thinking about and building real world stuff with it. This is the reason I'm asking here, rather than SO so people can follow along - and it doesn't get closed as too general :-). I will attempt to roll all of the good stuff from the conversation here - if any into the documentation.

Thanks all, Ben

submitted by b00thead
[link] [23 comments]

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Greetings, We can currently do something like This means that our `a' has to be an instance of Num and Eq. Apologies for a bit of an artificial example. Is there a way however to do something along the lines of: This would allow us to make an instance of Num be an instance of Foo or an instance of Eq to be an instance of Foo. The compiler currently complains about multiple declarations. Is there currently a way to achieve this? The main issue I can see with this is that given an instance of both, Num and Eq, it wouldn't be possible to pick the correct default implementation. Purely a theoretical question. - -- Mateusz K. -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.19 (GNU/Linux) iQIcBAEBAgAGBQJRjP0hAAoJEM1mucMq2pqX30wP/0d0TQHs4S3G5TBw+T1baI6n g/5k/YlPmSgS3FaO8JMQsb2uqL8dGPZGUN7d2ohwcigtXS88KWH4u4rTjrs1+p8o ktS+vIE4kEEedTAX6wmP2Zn+rvK2zFGboCafaX/a/IxT5CbwYZ97RrWCjzz1jlPs S/VlhNHcTQ7Cf/0pa0xJ1kbao+vBHiWtWjxcdzCT/6zS86+jm9vz8qrYT3TWUd3y AJXPBjRuXeyz+

I've been working on a new Haskell interface to the linux kernel's inotify system, which allows applications to subscribe to and be notified of filesystem events. An application first issues a system call that returns a file descriptor that notification events can be read from, and then issues further system calls to watch particular paths for events. These return a watch descriptor (which is just an integer) that can be used to unsubscribe from those events. Now, of course an application can open multiple inotify descriptors, and when removing watch descriptors, you want to remove it from the same inotify descriptor that contains it; otherwise you run the risk of deleting a completely different watch descriptor. So the natural question here is if we can employ the type system to enforce this correspondence. Phantom types immediately come to mind, as this problem is almost the same as ensuring that STRefs are only ever used in a single ST computation. The twist is that the inotify interface h

submitted by silentbicycle
[link] [1 comment]

I'm trying to find my way around Template Haskell, so after discovering that all the liftA* functions can be built from just pure and <*> like this:

fp a b = a . <*> . b liftA = fp id pure liftA2 = (fp . fp) id pure liftA3 = (fp . fp . fp) id pure

et cetera, I decided to make a liftA* function generator in template haskell. The code is here - it defines functions named liftA', liftA2', etc.

I found it difficult to figure out when to use functions like varT, appT, etc., and when to use the data constructors VarT, AppT, etc. The version I have now almost exclusively uses the lowercase functions that operate inside the Q monad but my code went through several iterations to get there and I'm not sure that's the right choice.

I'd appreciate people with TH experience taking a look and commenting on my approach to the extent that it's possible to do so with such a small code sample.

submitted by fizbin
[link] [2 comments]

I would like to propose the addition of whenJust :: Monad m => Maybe a -> (a -> m ()) -> m () whenJust (Just x) f = f x whenJust _ _ = return () to Control.Monad, in the section "Conditional execution of monadic expressions" next to guard :: MonadPlus m => Bool -> m () when :: Monad m => Bool -> m () -> m () unless :: Monad m => Bool -> m () -> m () Why? It would allow us to write more readable code and fit well into the group of similar functions of this style. Compare mUser <- lookupUser whenJust mUser email or whenJust mUser $ \user -> do putStrLn "Mailing!" email user with some currently available alternatives: case mUser of Just user -> do putStrLn "Mailing!" email user Nothing -> return () (Default base case clutter.) import Data.Foldable forM_ mUser $ \user -> do putStrLn "Mailing!" email user (Not too intuitive/well-named here and "Ambiguous occurrence forM_" clash with Control.Monad.)

Hello Cafe, I came up with (actually reinvented [1]) a solution to configuration problem. For example configuration: data Config = Config { port :: Int, verbosity :: Int, logfile :: FilePath } deriving Show the basic idea is to use implicit parameters: runServer :: (?config :: Config) => IO () The problem is that it is tiresome to decorate all functions in this way. It is also non composable. For example if we switch to using two separate configuration entities like this: data LogConfig = LogConfig { verbosity :: Int, logfile :: FilePath } data NetConfig = NetConfig { port :: Int } we suddenly have to fix types all over the place. Yuck. The extended idea here (compared to [2]) is to use type synonym with all required parameters. This is simple (but requires at least Rank2Types): type ConfIO a = (?config :: Config) => IO a All the functions requiring config will now be simply in ConfIO monad which is really IO with a bonus. A great feature of this solution is that we don't need to use liftIO anywher

Hi. Does Haskell allow you to flip around type parameters somehow? I was playing around with toy code (still learning the fundamentals) and I came up with a class like this: code: -------- class Rotatable2D a where rotate :: (Num b) => (a b) -> b -> (a b) -------- It was easy to make an instance of a generic single-parameter type: code: -------- data Angle a = Angle a deriving (Show) instance Rotatable2D Angle where rotate (Angle a) b = Angle (a + b) -------- But let's say I have something a little more complicated: code: -------- data CircAppr a b = CircAppr a a b -- radius, rotation angle, number of points -------- I think I need something like so: -------- instance Rotatable2D (\x -> CircAppr x a) where rotate (CircAppr a b c) d = CircAppr a (b + d) c -------- But I tried that and it isn't valid syntax.

Eschersketch, by Anselm Levskaya.  Spotted via Boing Boing.