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.

85 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
  2. Great post! I didn’t knowral of these resources and I’m going to go check them out now!

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

    ReplyDelete
  4. 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
  5. this is really appriciate this work
    thanx for sharing this
    myassignmenthelp refund visit my site and know more about myassignmenthelp

    ReplyDelete
  6. 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
  7. This comment has been removed by the author.

    ReplyDelete
  8. 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


  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. ​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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. Here is a bit by bit manual for download and introduce HP Deskjet 3700 wireless setup on Windows, Linux and Mac OS X.

    ReplyDelete
  23. 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
  24. Updated version of Test Bank For Macroeconomics 12th Edition available for instant download. Avail great discounts and offers now.

    ReplyDelete
  25. Global Assignment Expert offers law assignment help which deals with the rules and regulations, acts and sections provides in the rule book. Our Law experts will support administrative law, tax law, Contract Law, Family Law, Property Law ,Insolvency Law, Tort Law, Equity Law, and many more. We have a panel of assignment help experts for law assignments because the content needs proper investigation with depth knowledge. We never compromise with the quality we always deliver the best in quality. We provide a complete solution with proper clarification. Our support team will always be ready to clarify your doubts.

    ReplyDelete
  26. We can assist you with your assignments instead of you having to travel all over the place. Our assignment help in australia is accessible through the Internet. We can provide better service for used services.

    ReplyDelete
  27. My name is Linnea! Our company has a team of professional online assignment helpers. Our online platform provides you with the ability to hire writers to assist with your supply and demand assignments. We have highly qualified experts who can assist you with writing your assignments. Your assignments will be of the highest quality when they are written by our experts.

    ReplyDelete
  28. College task composing administrations are trusted the most due to the select quality which is mind-blowing by any understudy. The specialists realize all around ok with regards to how the tasks must be made to focus on the quality and this is reflected to the center in the work introduced finally. myassignmenthelp

    ReplyDelete
  29. This page provides magha nakshatra in hindi dates with start and end timings in the year 2021 for Mountain View, California, United States.

    ReplyDelete
  30. Get help for science assignments only at the "Best Assignment Experts" website where only the professional experts provide the Science Assignment Help.

    ReplyDelete
  31. Thank you for this blog I always recommend this to my friends and if anyone need help in Homework please recommend our website Canada Assignment Help we provide best Homework Help service to the Canadian students.

    ReplyDelete
  32. Roadseal civil We proudly provide services that keep our community moving, with expertise in constructing hardstands, carparks, roads and driveways. We primarily service Melbourne metro, Geelong, Ballarat, Bendigo, Warragul and Mornington regions.
    READ MORE :- Asphalt Driveways

    ReplyDelete
  33. My Assignment Experts is a leading Australian and UK Online assignment help service for students. Our Ph.D. assignment experts can support you with almost any subject or question.

    ReplyDelete
  34. Essay Helper – 24/7 Here for You! Our essay writing assist carrier is the first-class answer to your trouble of essay writing help our Writer – Ready to Work! Choose your private assistant at

    ReplyDelete
  35. Our Geography Assignment Help Service is available at all times. To provide you with Geography online assignment assistance, Our Geography Assignment Experts always available Our Geography professionals can help academic students get a higher level of training by assisting them with Geography and other topics assignments.

    ReplyDelete

  36. Custom paper boxes include the customization or personalization of using various attractive and beautiful designs. A mono colored, blank and simple paper Custom boxes is never in demand as compared to a modified, designed and personalized designs.

    ReplyDelete
  37. Here you can get the best deal. Get best fitness band under 2000 in india and measure your workout, heart rate, calories in one device. Buy the best fitness band in india under 2000 to keep accountability of your fitness routine. Get the best band now! best fitness band under 2000 in india

    ReplyDelete
  38. This is again a great post by you. I'm a regular visitor of your website. Keep it up and keep sharing such posts.
    Sometimes students take assignment help to deliver their assignment on time.
    There are many tough subjects where students seek for online assignment help like Civil Engineering Assignment Help, MYOB Assignment Help, HR Assignment Help and etc.

    ReplyDelete
  39. Really Good Work Done By You...However, stopping by with great quality writing, it's hard to see any good blog today.
    PROcrackerr
    Helium Music Manager CRACK

    ReplyDelete
  40. Are you Looking For online assignment help in Canada? Then, don't worry we have a specialized team for assignment help support and they provide you service 24/7 to students. So hurry up and get in touch soon at Canada Assignment Help.

    ReplyDelete

  41. Min veninde fik en virkelig lækker steak, som jeg fik lov at smage. take away lyngby Der var også et lækkert vegetarisk udvalg derudover var servicen som jeg aldrig har prøvet før, med de sødeste og mest opmærksomme tjenere! Jeg vil helt klart komme på Bindia igen!
    Vinyl comes in nearly every color imaginable, and there are also wholesale v necks t shirts products that contain glitter or flocking. If you’re looking for versatility and the ability to create fun, textured designs, consider vinyl.

    ReplyDelete
  42. Og gå ikke glip af deres skønne cheesecake, take away Nørrebro der lige sætter en vidunderlig prik over i’et på en vellykket aften.
    Cheap Polo Shirts Blankstyle has a large selection of wholesale polo shirts to fit both your high quality hoodies wholesale budget and your project needs ranging from cheap to high end.

    ReplyDelete


  43. We have talked with one of the Oily skin person Rosy. "My skin was so oily since childhood and it was really irritating for me. I can't be confident even while i go to party or else to a function, everyone stares at my oil skin and i have to feel the shy. This is where I came across the best Skin Care Products from the Yuglo skin where the best Face Oil is one of the best products which makes my face very smooth, free from oil and looks so great. Since then I have become an evid fan of the natural skin care brand. Especially the Natural Ingredients makes the brand so unique because these days we are seeing so many chemicals used products. Even though, their results might be faster but in the long run, we are going to have issues while using such kind of brands. Hence I recommend Yuglo for any women who is looking for organic and natural products for their hair, face and skin".

    While when we got the opportunity to speak with one of the dry skin women Ily. Ily said "My skin was dry all the time and it is really frustrating experience for me, especially, I stay in the cold regions and when there is heavy cold, you can clear see the layers coming out from the lips and skin due to dryness, that is where i tried the Lip mask from the Yuglo. I apply it at thee night time before i sleep and while i woke up in the morning, i am going to have a great and nice experience, My skin feels better and i also tried the  skincare Facemask from this organic brand. I applied it for a month and you don't and you don't believe me the results are fantastic. I am using both their Peach Lips mask and Face mask for the skin since past 2 years and i would love to try their new products as well in the future. Thanks to the yuglo skin for bringing such awesome products and great thing is they are available at an affordable pricing. It merely costs me $25 per month to try their products and have a healthy skin routine.



    When it comes to the types of the products, there are so many people who are trying the natural face masks by seeing the youtube videos and improving their skin care. There are majorly three types of skins, one is oily, the other is dry and the third one is mixed. Especially those with Oily skin always suffer due to their face looks quiet odd due to the excess oil on their face and they feel so bad about it. The same is the case with the dry skin people too, their skin becomes so dry and can see the layers coming out from their face and especially lips during the winter time, it is going to be so heavy.
      
    This is where the Organic products of skin care has come in handy for these kind of people. While people who are having a mixed dry and oily skin, not had to suffer much but still they can improve their skin tone using the Lips mask product from amazon. This product is bought by more than 100000+ happy customers and has an average rating of 4.5 with more than 5500 reviews. This product is from natural skin care brand Yuglo.

    They have products which are related to hair, face and lips. Especially their lip sleeping mask is the best seller and next comes, the face mask which is also quiet good seller for them. They also have face oil and new vanilla flavor for the lips, they want to become one of the top skin care brands in the future by solving all the issues related to the skin care. They also have the face moisturizer which is one of the best among the face moisturizers compared to others as those comes with the natural ingredients which everyone will love than compared to unnatural and chemical ingredients.

    ReplyDelete
  44. Great post. I was checking continuously this blog and I am impressed! Very useful info specifically the last part :) I care for such info much. I was looking for this certain information for a very long time. Thank you and best of luck. Get It SMS is a India No 1 Bulk SMS Service Provider in Kolkata. Bulk SMS is considered to be the latest method to advertise and promote products and services. The far reaching impact of cell phones which have transformed the perception of communication as led to the popularity of this new marketing tool. Organisations pertaining to various sectors like Finance, retail, healthcare, automobile and many more are resorting to bulk SMS as a cheap, reliable, convenient and fast way to promote and advertise their products. Bengaluru with its open environment of welcoming change has taken the gamble and benefited by it. Various business houses based out of Bengaluru have witnessed positive results in the form of sales conversions. Moreover, Bulk SMS Service Provider in Delhi have managed to reach the right people with the right information and at the right time. Bulk SMS Service Provider in Mumbai has witnessed a success rate far higher than any other forms of marketing carried out in the city. A large part of this is attributed to the motley population residing in and around the city. These growing sections of IT professionals who migrate to this IT city every year have given it a distinct character. The lazy laid back environment that once characterised the place is being very soon replaced with a fast paced frenzy. People are becoming increasingly pressed for time. The conventional marketing techniques have long become back dated. Organisations therefore need to think of innovative methods to promote their products in order to remain in consumer memory. Bulk SMS is one such innovation that both organizers have adopted and consumers have accepted. Best OTP SMS Service Provider in India can your business to deliver the best services for your business all the time. So, if you look at the results of one time password SMS service. This has provided excellent service in security to the businesses.

    ReplyDelete
  45. Модет вам пригодится статья о табаке щербет https://hookahcat.com.ua/

    ReplyDelete
  46. At Acadecraft, clients can avail the best mobile learning company. Adhering to the requirements, the company develops customized mobile learning solutions that engage the learners.
    For free quotes and samples, reach out to the company at info@acadecraft.com.

    Also Read: e learning services company

    ReplyDelete
  47. With the most population per square mile in the United States, California has a unique mix of safety concerns for residents and businesses alike. That's why the people of this state rely on Mission Protection Services to provide reliable, professional security guards who Best Armed Security Guards Services San Diego can help them deal with these issues.

    ReplyDelete
  48. Hi there! I just want to offer you a huge thumbs up for the great information you have here on this post. I’ll be coming back to your website for more soon.
    출장샵
    출장샵
    출장샵
    출장샵
    출장샵
    출장샵

    ReplyDelete
  49. I'm unsure which assignment help service in CanadaAssignment help canada is best. Get in contact with our professionals right now for top-notch support, advice, and answers to your academic problems.
    My Assignment help

    ReplyDelete
  50. We are ready to keep you, your property, and your possessions protected and secure with our firewatch security officer services for any industry Shopping Center Security that you may require. FireWatch Security LA is one of Los Angeles Top FireWatch Security Guard Companies that are ready to keep you, your property, and your possessions protected and secure with our fire watch security officer services for any industry that you may require.

    ReplyDelete
  51. Marketing Assignment Help Uk provides you with the assignment services because marketing assignment is the process of developing, planning, strategies, analysis, and implementation of programs. Our assignment helpers are highly experienced in their own field. They are highly efficient in the field. So hurry up and visit our website.

    ReplyDelete
  52. Hey there! I simply wish to offer you a big thumbs up for the excellent random functions you have shared right here. Looking forward to more reviews. Thank you so much for sharing. college of health science jahun admission form

    ReplyDelete
  53. This function is often used in programming languages to evaluate whether a given value is true or false. In general, it will return true if the value is not null and false otherwise. The main function should be used in conjunction with other functions. The main function should always be at the top of a program because it has to be called first before other functions are called. Most students are drawn to these types of articles and information, but they are unable to prepare for their exams, If you have been struggling with your exams and want assistance, students can hire someone to hire someone to do my online class and get higher grades on their examinations by providing them with the best available resources, including quality academic services.

    ReplyDelete
  54. The Online M.Tech Course in Electrical Power Electronics is a great way to gain expertise in the field of power electronics. This course will provide students with an understanding of the fundamentals of electrical power systems, and how they can be used to design and develop efficient and reliable solutions for various applications. Students will learn about the different components used in power electronics, such as transistors, diodes, capacitors, inductors, and other components. They will also learn about the principles behind their operation and how they can be used to control electric current flow. Furthermore, students will get an overview of modern technologies like digital signal processing (DSP) and microcontrollers (MCUs). With this knowledge, they will be able to design efficient solutions for a wide range of applications.

    ReplyDelete

  55. Thanks for posting this educative writeup.

    ReplyDelete
  56. Thanks for sharing this marvelous post.

    ReplyDelete
  57. You have touched some pleasant factors here.

    ReplyDelete
  58. It’s perfect time to make a few plans for the future and it is time to be happy.

    ReplyDelete
  59. Moreover, many online courses provide practical applications and use cases for generating random functions. This means that you won't just be learning theoretical concepts but also gaining hands-on experience by applying what you've learned in real-world scenarios.

    So if you're feeling overwhelmed or unsure about how to generate random functions, consider enrolling in an Do my online course. It's a convenient and effective way to enhance your understanding and master this important skillset. Don't let complexity hold you back - take charge of your learning journey today!

    ReplyDelete
  60. Thanks for sharing the useful information. to find best mortgage calculator Visit realoq.com

    ReplyDelete
  61. Thanks for sharing and keep it up like this.

    ReplyDelete
  62. I’m certainly happy I came across it

    ReplyDelete
  63. I’ll be bookmarking it and checking back regularly!

    ReplyDelete
  64. Hello, I’m happy to see some great articles on your site.

    ReplyDelete
  65. I would like to thnkx for the efforts you have put in writing this blog.

    ReplyDelete
  66. I am hoping the same high-grade blog post from you in the upcoming as well.

    ReplyDelete
  67. I hope this think help any newbie for their awesome work.

    ReplyDelete
  68. By the way thanks for share this awesomeness from Feel free to visit my website;

    ReplyDelete
  69. It is an amazing site and superior to anything normal give. I need to grateful

    ReplyDelete