Thursday, February 2, 2012

Generating random functions

How can we pick a random Haskell function? Specifically, we want to write an IO action

randomFunction :: IO (Integer -> Bool)

with this behavior:

  • It produces a function of type Integer -> Bool.

  • It always produces a total function — a function which never throws an exception or enters an infinite loop.

  • It is equally likely to produce any such function.

This is tricky, because there are infinitely many such functions (more on that later).

In another language we might produce something which looks like a function, but actually flips a coin on each new integer input. It would use mutable state to remember previous results, so that future calls will be consistent. But the Haskell type we gave for randomFunction forbids this approach. randomFunction uses IO effects to pick a random function, but the function it picks has access to neither coin flips nor mutable state.

Alternatively, we could build a lazy infinite data structure containing all the Bool answers we need. randomFunction could generate an infinite list of random Bools, and produce a function f which indexes into that list. But this indexing will be inefficient in space and time. If the user calls (f 10000000), we'll have to run 10,000,000 steps of the pseudo-random number generator, and build 10,000,000 list elements, before we can return a single Bool result.

We can improve this considerably by using a different infinite data structure. Though our solution is pure functional code, we do end up relying on mutation — the implicit mutation by which lazy thunks become evaluated data.

The data structure

import System.Random
import Data.List ( genericIndex )

Our data structure is an infinite binary tree:

data Tree = Node Bool Tree Tree

We can interpret such a tree as a function from non-negative Integers to Bools. If the Integer argument is zero, the root node holds our Bool answer. Otherwise, we shift off the least-significant bit of the argument, and look at the left or right subtree depending on that bit.

get :: Tree -> (Integer -> Bool)
get (Node b _ _) 0 = b
get (Node _ x y) n =
case divMod n 2 of
(m, 0) -> get x m
(m, _) -> get y m

Now we need to build a suitable tree, starting from a random number generator state. The standard System.Random module is not going to win any speed contests, but it does have one extremely nice property: it supports an operation

split :: StdGen -> (StdGen, StdGen)

The two generator states returned by split will (ideally) produce two independent streams of random values. We use split at each node of the infinite tree.

build :: StdGen -> Tree
build g0 =
let (b, g1) = random g0
(g2, g3) = split g1
in Node b (build g2) (build g3)

This is a recursive function with no base case. Conceptually, it produces an infinite tree. Operationally, it produces a single Node constructor, whose fields are lazily-deferred computations. As get explores this notional infinite tree, new Nodes are created and randomness generated on demand.

get traverses one level per bit of its input integer. So looking up the integer n involves traversing and possibly creating O(log n) nodes. This suggests good space and time efficiency, though only testing will say for sure.

Now we have all the pieces to solve the original puzzle. We build two trees, one to handle positive numbers and another for negative numbers.

randomFunction :: IO (Integer -> Bool)
randomFunction = do
neg <- build `fmap` newStdGen
pos <- build `fmap` newStdGen
let f n | n < 0 = get neg (-n)
| otherwise = get pos n
return f

Testing

Here's some code which helps us visualize one of these functions in the vicinity of zero:

test :: (Integer -> Bool) -> IO ()
test f = putStrLn $ map (char . f) [-40..40] where
char False = ' '
char True = '-'

Now we can test randomFunction in GHCi:

λ> randomFunction >>= test
---- -   ---   -    - -   - --   - - -  -- --- -- --          - -- - - --  --- --
λ> randomFunction >>= test
-   ---- - - - -  - - -- -   -     ---  --- -- - --  -  --    - -  - - -  --   - 
λ> randomFunction >>= test
- ---  - - -  --  ---         -  --  -  -    -  -  - ---- - -  ---   -     -    -

Each result from randomFunction is indeed a function: it always gives the same output for a given input. This much should be clear from the fact that we haven't used any unsafe shenanigans. But we can also demonstrate it empirically:

λ> f <- randomFunction
λ> test f
-   -----  - -   -- - -   --- --  - -   - -   - -   -- - -   ---- - - - -  - --- 
λ> test f
-   -----  - -   -- - -   --- --  - -   - -   - -   -- - -   ---- - - - -  - --- 

Let's also test the speed on some very large arguments:

λ> :set +s
λ> f 10000000
True
(0.03 secs, 12648232 bytes)
λ> f (2^65536)
True
(1.10 secs, 569231584 bytes)
λ> f (2^65536)
True
(0.26 secs, 426068040 bytes)

The second call with 2^65536 is faster because the tree nodes already exist in memory. We can expect our tests to be faster yet if we compile with ghc -O rather than using GHCi's bytecode interpreter.

How many functions?

Assume we have infinite memory, so that Integers really can be unboundedly large. And let's ignore negative numbers, for simplicity. How many total functions of type Integer -> Bool are there?

Suppose we made an infinite list xs of all such functions. Now consider this definition:

diag :: [Integer -> Bool] -> (Integer -> Bool)
diag xs n = not $ genericIndex xs n n

For an argument n, diag xs looks at what the nth function of xs would return, and returns the opposite. This means the function diag xs differs from every function in our supposedly comprehensive list of functions. This contradiction shows that there are uncountably many total functions of type Integer -> Bool. It's closely related to Cantor's diagonal argument that the real numbers are uncountable.

But wait, there are only countably many Haskell programs! In fact, you can encode each one as a number. There may be uncountably many functions, but there are only a countable number of computable functions. So the proof breaks down if you restrict it to a real programming language like Haskell.

In that context, the existence of xs implies that there is some algorithm to enumerate the computable total functions. This is the assumption we ultimately contradict. The set of computable total functions is not recursively enumerable, even though it is countable. Intuitively, to produce a single element of this set, we would have to verify that the function halts on every input, which is impossible in the general case.

Now let's revisit randomFunction. Any function it produces is computable: the algorithm is a combination of the pseudo-random number procedure and our tree traversal. In this sense, randomFunction provides extremely poor randomness; it only selects values from a particular measure zero subset of its result type! But if you read the type constructor (->) as "computable function", as one should in a programming language, then randomFunction is closer to doing what it says it does.

Edit: See also Luke Palmer's recent article on this subject.

See also

The libraries data-memocombinators and MemoTrie use similar structures, not for building random functions but for memoizing existing ones.

You can download this post as a Literate Haskell file and play with the code.

62 comments:

  1. The set of total Haskell functions may not be recursively enumerable, but choose some total language (say, System F with structural recursion). The set of total functions in this language *is* recursively enumerable--generate a function and type check it. If it passes type checking, it's total.

    That is, we have

    interpret :: SystemFExpression -> Integer -> Bool
    generate :: Integer -> SystemFExpression

    However, we still haven't reached a contradiction; the diagonalization argument requires us to find an N such that (generate N) generates the function with source code:

    [code for interpret]
    [code for generate]
    f n = not (interpret (generate n) n)

    But any language that can implement its own interpreter isn't total!

    ReplyDelete
    Replies
    1. Great Article android based projects

      Java Training in Chennai Project Center in Chennai Java Training in Chennai projects for cse The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training Project Centers in Chennai

      Delete
  2. Nice article, thanks for the information. It's very complete information. I will bookmark for next reference
    jaring futsal | jaring golf | jaring pengaman proyek |
    jaring pengaman bangunan | jaring pengaman gedung
    http://www.jual-jaring.blogspot.com/
    http://www.agen-jaring.blogspot.com/
    http://www.pancasamudera-safetynet.blogspot.com/
    http://www.toko-jaring.blogspot.com/
    http://www.pusat-jaring.blogspot.com/
    http://jualjaringpengaman.blogspot.com/
    https://pancasamudera.wordpress.com/
    https://pasangjaringfutsal.wordpress.com/
    https://jualtambangmurah.wordpress.com/
    https://tokojaring.wordpress.com/
    https://jualjaringfutsal.wordpress.com/
    https://jaringfutsal.wordpress.com/


    ReplyDelete
  3. Great post! I didn’t knowral of these resources and I’m going to go check them out now!

    ReplyDelete
  4. Thank you for the valuable information.iam very much impressed with this one.
    Looking forward for the good posts.
    gbwhatsapp benefits

    ReplyDelete
  5. Packers and Movers Bangalore - Reliable and Verified Household Shifting Service Providers Give Reasonable ###Packers and Movers Charges. Cheap and Best Office Relocation Compare Quotation for Assurance for Local and Domestic House Shifting and Get estimates today to save upto 20%, ***Read Customer Reviews - @ Local Packers And Movers Bangalore

    ReplyDelete
  6. great stuff men
    looking forward more
    thanx for sharing this
    if you looking geohraphy assignment help so hire experts from myassignmenthelp and get the best result

    ReplyDelete
  7. this is really appriciate this work
    thanx for sharing this
    myassignmenthelp refund visit my site and know more about myassignmenthelp

    ReplyDelete
  8. hey this is very helpful post
    if you are looking for
    assignment help
    so hire our experts and get the best results and got high marks

    ReplyDelete
  9. Suggest good information in this message, click here.
    auteursdejeux.com
    carrymyad.com

    ReplyDelete
  10. Scholars need to connect with effective online assignment writing for do my assignment query. For that, visit website of online service providers and check their reliability before placing your order for any subject.

    ReplyDelete
  11. Now that is what I call a smooth write-up. Talk about smooth write-ups, if you want to maintain a smooth sail in your academic writing tasks as well you can get in touch with the deft Academic Dissertation Help experts of the LiveWebTutors platform and receive flawless solutions for your daunting assignments in just a few clicks.

    ReplyDelete
  12. I enjoyed reading your post. I was also struggling with my scholarly assignments just as you stated in your post but luckily, I stumbled across the online Assignment Help facility by the MyAssignmentHelpAu platform. Their skilled subject-specific experts leave no stone unturned to deliver accurate assignment solutions that can easily impress your professors and mentors. You can order any assignment format for any subject area from this portal and improve your academic grades remarkably.

    ReplyDelete
  13. Are you searching for Assignment Help online in Canada? Then you are in the right spot. Our team of professional writers is highly efficient in helping the students with their assignments. Visit our website to know more about our services.

    ReplyDelete

  14. Online Essay Help Singapore help and submitting tasks and articles before the cutoff time is a difficult one to figure out. It takes extraordinary commitment.
    Consider the possibility that, you don't have much homework help Australia. Imagine a scenario where, you have arranged things that are conflicting with your courses.
    AConsider the possibility that, you are routinely getting less evaluations your courses. On the off chance that this sounds you fit, at that point you ought to likely
    take Statistics homework help Australia from GOTOASSIGNMENTHELP specialist co-op. It can remove all the torment you are in. You can get copyright infringement free
    task and My Assignment Help Singapore and that too with high caliber. This can presumably bring A+ Essay Help Singapore and you can wander gladly with best assignment help Australia under your arm.

    ReplyDelete
  15. Scholars need to connect with effective online assignment writing for do my assignment query. For that, visit website of online service providers and check their reliability before placing your order for any subject.

    ReplyDelete


  16. Research assignment helphelp and submitting tasks and articles before the cutoff time is a difficult one to figure out. It takes extraordinary commitment.
    Consider the possibility that, you don't have much homework help Australia. Imagine a scenario where, you have arranged things that are conflicting with your courses.
    AConsider the possibility that, you are routinely getting less evaluations your courses. On the off chance that this sounds you fit, at that point you ought to likely
    take Statistics homework help Australia from GOTOASSIGNMENTHELP specialist co-op. It can remove all the torment you are in. You can get copyright infringement free
    task and Essay writing service Australia
    and that too with high caliber. This can presumably bring A+ Essay Help Singapore and you can wander gladly with best assignment help Australia under your arm.

    ReplyDelete


  17. University assignment help and submitting tasks and articles before the cutoff time is a difficult one to figure out. It takes extraordinary commitment.
    Consider the possibility that, you don't have much homework help Australia. Imagine a scenario where, you have arranged things that are conflicting with your courses.
    Consider the possibility that, you are routinely getting less evaluations your courses.
    Assignment maker Aaustralia
    On the off chance that this sounds you fit, at that point you ought to likely
    take Statistics homework help Australia from GOTOASSIGNMENTHELP specialist co-op. It can remove all the torment you are in. You can get copyright infringement free

    ReplyDelete
  18. Not sure which is the best Assignment Help canada in Canada. Get in touch with our experts now and receive top-notch quality assistance and guidance, along with solutions to your academic issues.

    ReplyDelete
  19. Accounting assignment help allows you to connect with experts and get effective assistance for your project submission. Don’t forget to check out all the features before buying the services of online assignment help for your accounting papers.

    ReplyDelete
  20. If your consistent efforts are not actually turning into the outcomes you are looking for, it’s a sign that you need an expert to guide you. Our experts at Help in homework are ready to offer you paper writing services at the best market price. Wherever you are located in Australia and whatever your academic needs are, you can trust our experts to get it done and help you score top grades. Help in homework will be your trusted solution provider from now on.

    ReplyDelete
  21. Well, Now you need not to worry about your pending assignment writing.assignment help is one of the best assignment service provider in UK. We are here to give you best nursing assignment Help. Browse our services of assignment help London, Edinburgh, Manchester and Across UK.

    ReplyDelete
  22. If your consistent efforts aren't yielding the results you want in your job seeking campaign, it's time to seek for professionals. Our online jobs portal are here to assist you with the hundreds of latest jobs you might get some great recruitments to get successful and landing for a suitable employment in programming.

    ReplyDelete
  23. Do you also want to take online Assignment help? Then don’t worry, we will help you! We offer you the best assignment writing services at a very low price. Browse our website for taking the best assignment writing help.

    ReplyDelete
  24. Do you find it hard to seek a reliable academic writer in Singapore? The easiest way to overcome the academic-related issues of Singapore universities are Assignment Help . Generally, scholars choose different countries to pursue their higher studies to get remarkable career opportunities.

    ReplyDelete
  25. Are you unable to get Assignment help UK? Don’t worry! We offer you the best quality assignment assistance. We have highly qualified writers who will provide you supreme quality help regarding your assignment.

    ReplyDelete
  26. Posting such good information and helping every person who is looking for the best Car Transport Pune. Logistics guru is the best service provider that deals with affordable car transportation services. The company tends to cover a wide range of services. Here is the website link, click on it. You can get a lot of information.

    ReplyDelete
  27. Hard exams, assignments and homework are a now things of the past with Operations Management For Mbas 5th Edition Test Bank. Order and download now!

    ReplyDelete

  28. There are few more ways by which you can utilize online academic Singapore assignment help and get the desired results that you want. Your knowledge will increase if you have academic writing assistance.

    ReplyDelete
  29. ​The quickest way to earn better grades is to avail ​Homework Help. Look no further, just visit ScholarOn and be the top student in your class.

    ReplyDelete
  30. I blog often and I truly appreciate your content.
    야설

    Also visit my web site;
    야설

    ReplyDelete
  31. This great article has truly peaked my interest.
    일본야동
    Also visit my web site 일본야동

    ReplyDelete
  32. I’m going to bookmark your site and keep checking for new details about once per week.
    국산야동
    Also visit my web site 국산야동

    ReplyDelete
  33. I subscribed to your Feed too.

    일본야동
    Also visit my web site 일본야동

    ReplyDelete
  34. Opt for our Assignment Help to finish your assignments and submit them within the deadline. No need to take the stress of insufficient knowledge and lack of skills when you have an online assignment writing expert for writing your assignment in Qatar.

    ReplyDelete
  35. Such an amazing and helpful post this is. I really really love it. It’s so good and so awesome.I am just amazed. I hope that you continue to do your work like this in the future also. 온라인카지노

    ReplyDelete
  36. I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job ! 온라인카지노

    ReplyDelete
  37. Such an amazing and helpful post this is. I really really love it. It’s so good and so awesome. I am just amazed.
    Try to visit my post
    foods to avoid for kidney health

    ReplyDelete
  38. We have an advanced experienced to give incredible assignment writing administrations through our accomplished, qualified and very much prepared group of assignment writing specialists. We have an advanced encounter of serving students from various college across the globe. australian assignment help

    ReplyDelete
  39. You can find Cornerstones Of Managerial Accounting Available Titles Aplia 3rd Edition Test Bank online in pdf/word format. Avail instant assistance for issues 24/7. There is no waiting time!

    ReplyDelete
  40. Do not waste countless hours on your college assignments anymore. Get Solution Manual For International Business Competing In The Global Marketplace 10th Edition and work smart with better results.

    ReplyDelete
  41. Here is a bit by bit manual for download and introduce HP Deskjet 3700 wireless setup on Windows, Linux and Mac OS X.

    ReplyDelete
  42. I am stresses for the long time and do not idea how to tackle academic responsibility. I have gone through your site and find its inspiring post to make creative content. Meanwhile, you go through Assignment Help navigational link available on our website.

    ReplyDelete
  43. Gotoassignmenthelp is team of leading professional writers for academic assignment help Australia Writing Services to students all around the world. Contact us today for Best University assignment help Australia at very affordable price. Under GotoAssignmentHelp we provide many types of help to the students. We are the most reliable assignment helpers. We have gained our specialization after spending most of our times in making ourselves perfect. We providing 100% plagiarism free Assignment Help. At the point when you pick our Assignment assistance assistance, our faculty will consider the quality and your evaluation criteria.

    ReplyDelete
  44. Updated version of Test Bank For Macroeconomics 12th Edition available for instant download. Avail great discounts and offers now.

    ReplyDelete
  45. I cannot write my assignment and assignment help online. Don't worry we will offer you the best writing facilities in your budget. Our team of writers can provide you the best writing assistance in your budget. Take help from us and submit plagiarism-free assignments.

    ReplyDelete
  46. The secret for student success lies in the material you use for learning.Try Test Bank For Essentials Of Business Communication 9th Edition and feel the difference.

    ReplyDelete
  47. Marketing assignment includes many topics and extensive research, which makes the hectic burden on the student’s head. If you are a student and want help with marketing assignments., it is better to help an expert. Students primarily seek the best marketing assignment expert to help the students get good grades without any tension. An essential part of seeking help for the assignment is hiring the right one. The Internet provides you various kinds of information. It offers several services, and you have to verify the company's details before assigning your marketing assignment to the service.

    ReplyDelete
  48. Thanks for sharing amazing tips. Following this step will transform the standard of your MyAssignmentHelpsAu platform for sure. Wow, marvelous weblog layout! You made blogging glance easy. Please keep sharing more and more information. I will bookmark your web page regularly and maintain checking for new updates. Enjoyed reading it as it really explains everything in detail. My Assignment Help provided by expert is very interesting and effective. Thank you and good luck with the upcoming blog.

    ReplyDelete