Making type-incompatible strategies interchangeable
# 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? 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())
Jacek Generowicz wrote:
# 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 -- http://apfelmus.nfshost.com
Warning! Incredibly hacky Haskell coming up! Here's some code that seems to do the near same thing as your Python. Below it is some sample output. A couple of differences are that the secret number should be between 1 and 10, and whenever the computer tries guess it just picks a random number until it get it right. Additionally the code maintains a record of wrong guesses in a list as opposed to an incrementing count. -deech {-# LANGUAGE ScopedTypeVariables, EmptyDataDecls, PackageImports #-} import Control.Monad.Random import "mtl" Control.Monad.State import "mtl" Control.Monad.Writer human_asker :: IO Int human_asker = do putStrLn "What's the secret number?" getLine >>= return . read randomNum :: Int -> Int -> IO Int randomNum low high = getStdRandom $ randomR (low, high) computer_asker :: IO Int computer_asker = randomNum 1 10 computer_guesser :: StateT Int (WriterT [Int] IO) () computer_guesser = do guess::Int <- liftIO $ randomNum 1 10 secret <- get process guess secret where process g s | g < s = do {tell [g]; liftIO $ putStrLn "Too low"; computer_guesser} | g > s = do {tell [g]; liftIO $ putStrLn "Too high"; computer_guesser} | g == s = do {liftIO $ putStrLn "Got it!"} human_guesser :: StateT Int (WriterT [Int] IO) () human_guesser = do guess::Int <- liftIO $ do {putStrLn "What's your guess?"; getLine >>= return . read;} secret <- get process guess secret where process g s | g < s = do {tell [g]; liftIO $ putStrLn "Too low"; human_guesser} | g > s = do {tell [g]; liftIO $ putStrLn "Too high"; human_guesser} | g == s = do {liftIO $ putStrLn "Got it!"} play asker guesser = asker >>= runWriterT . execStateT guesser -- # Output From Sample Runs
play human_asker computer_guesser What's the secret number? 10 Too low Too low Too low Too low Too low Too low Too low Too low Too low Too low Too low Too low Too low Too low Too low Too low Got it! (10,[3,8,7,7,1,5,8,6,4,7,1,8,5,7,2,3])
*Main> play computer_asker computer_guesser
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Too high
Got it!
(1,[4,10,2,10,8,10,6,6,3,7,2,6,3,4,9,4,8,6,7])
On Sat, Dec 18, 2010 at 7:31 AM, Heinrich Apfelmus
Jacek Generowicz wrote:
# 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
-- http://apfelmus.nfshost.com
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Excerpts from Jacek Generowicz's message of Fri Dec 17 20:17:30 -0500 2010:
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 ?
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
participants (4)
-
aditya siram -
Edward Z. Yang -
Heinrich Apfelmus -
Jacek Generowicz