[Haskell-cafe] Making type-incompatible strategies interchangeable
Jacek Generowicz
# by a human (alternatively, either locally, or remotely across a
# network). From Haskell's type system's perspective, these two will
# look completely different (most obviously, the human (or the
# network) is wrapped in IO). How can they be made interchangeable ?
# To demonstrate what I mean, I offer the following concrete toy
# example, in Python.
# It's a harness for playing the trivial higher-lower number guessing
# game, with interchangeable strategies for either player. In this
# example I provide two strategies (Computer / ask Human via IO) for
# each role (asker and guesser).
# How can this sort of interchangeability of computations which are
# conceptually identical, but incompatible from the types perspective,
# be expressed in Haskell?
from random import randint
# A simple game harness. It is given the two players, and mediates the
# interaction between them.
def game(asker, guesser):
feedback = None
count = 0
while not feedback == 0:
guess = guesser(feedback)
feedback = asker(guess)
print "Guess: %s, Answer: %s" % (guess, feedback)
count += 1
print "Got it in", count
# A couple of decorators to smoothe the use of the generators which
# are used to implement the players.
def hide_send(generator_function):
def proxy(*args, **kwds):
return generator_function(*args, **kwds).send
return proxy
def advance(hidden_send_proxy):
def proxy(*args, **kwds):
send = hidden_send_proxy(*args, **kwds)
send(None)
return send
return proxy
# Artificial player who knows the secret
@advance
@hide_send
def higher_lower_asker_C(low=0, high=100):
secret = randint(low, high)
guess = yield
while True:
guess = yield cmp(guess, secret)
# Artificial player trying to guess the secret
@hide_send
def higher_lower_guesser_C(low=0, high=100):
while True:
guess = (low + high) // 2
feedback = yield guess
if feedback < 0:
low = guess
else:
high = guess
# Interface to human who knows the secret
@advance
@hide_send
def higher_lower_asker_H():
guess = yield # No feedback before first guess
while True:
print "My guess is", guess
print "Please reply with one letter: is my guess (l)ow,
(c)orrect or (h)igh ?"
guess = yield {'l':-1, 'c':0, 'h':1 }[raw_input()]
# Interface to human trying to guess
@hide_send
def higher_lower_guesser_H():
while True:
feedback = yield input("What is your guess? ")
print {-1:"Too low.", 0:"Correct!", +1:"Too high."}[feedback]
# Given the above preparation, the game can now be played in all 4
# possible permutations of Computer/Human vs. Computer/Human.
game(higher_lower_asker_C(), higher_lower_guesser_C())
game(higher_lower_asker_H(), higher_lower_guesser_C())
game(higher_lower_asker_C(), higher_lower_guesser_H())
game(higher_lower_asker_H(), higher_lower_guesser_H())
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Heinrich Apfelmus
> # Imagine an activity which may be performed either by a computer, or
> # by a human (alternatively, either locally, or remotely across a
> # network). From Haskell's type system's perspective, these two will
> # look completely different (most obviously, the human (or the
> # network) is wrapped in IO). How can they be made interchangeable ?
>
> # To demonstrate what I mean, I offer the following concrete toy
> # example, in Python.
>
> # It's a harness for playing the trivial higher-lower number guessing
> # game, with interchangeable strategies for either player. In this
> # example I provide two strategies (Computer / ask Human via IO) for
> # each role (asker and guesser).
>
> # How can this sort of interchangeability of computations which are
> # conceptually identical, but incompatible from the types perspective,
> # be expressed in Haskell?
Have a look at my operational package, in particular the TicTacToe.hs
example on the examples page.
http://hackage.haskell.org/package/operational
(Unfortunately, the haskell.org domain is seized at the moment, so
this link won't work for a while. Also, please yell if you can't find
the examples page once the link works again.)
Regards,
Heinrich Apfelmus
Edward Z. Yang
> Imagine an activity which may be performed either by a computer, or
This particular example can be resolved from lifting the pure, computer
computation into IO. One way of abstracting this interaction is to use the Prompt
monad. [1]
This doesn't work in general, and indeed types do have the unfortunate property
of reducing modularity. This is especially evident when you work with dat
structures that have their invariants encoded in the type system. [2]
Or maybe this is a good thing, since you don't want IO leaking into your test
suite without you knowing about it...
[1] http://web.mit.edu/~ezyang/Public/threemonads.pdf
[2] http://www.cis.upenn.edu/~bcpierce/papers/harmful-mfps.pdf