How can I get a list of binary string depending on a number "n"?

Learn
1

I would like to write a function called “binary” which receives a natural number ‘n’, and return a list of 2^n binary string, for example:

binary 0 = [""]
binary 1 = ["0","1"]
binary 2 = ["00","01","10","11"]
binary 3 = ["000","001","010","011","100","101","110","111"]

etc

2

I’m assuming this is a homework question, so I don’t think it will help you much to give away the whole answer. I think you should be more clear about what parts of the question you are struggling with. Without that information it is very hard for us to help you.

One thing you can try is to solve a simpler problem. For example:

Write a function called “unary” which receives a natural number ‘n’ and returns a unary string of length n, for example:

unary 0 = ""
unary 1 = "1"
unary 2 = "11"
unary 3 = "111"

etc.

Are you able to solve that problem?

1 Like
3

You could provide an answer based on e.g. the Ackermann function (for acquiring some experience with recursion). The use of a zygohistomorphic prepromorphism is optional…

4

@atravers I’d love to see a solution using a zygohistomorphic prepromorphism. I’ve actually never seen it in practice :slight_smile:

5

I’ve written some code which does precisely this.

It consists of two parts:

  1. A recursive function which takes an integer and turns it into a string
  2. A function which maps the first function over a range

The first function has the following declaration (x is the integer, n is the number of zeros and ones in the string):

 conv2bin :: Int -> Int -> String -> String
 conv2bin _ 0 str = str
 conv2bin x n str =         -- left as an exercise for the reader

The second function is this:

  binary n = -- left as an exercise for the reader

Let us know how you get on.

6

Maybe one could be devised for a Haskell obfuscator which converts simple expressions into hideous monstrosities, complete with space-leaks, the odd call of a partial definition, etc…perfect for “homework answers”.

1 Like
7

@javimp2003 Did you manage to solve it yet? I would ignore these complex terms that people are suggesting here

1 Like
8

Have you noticed the following trend and it suggests a recursive strategy?

  binary 3
= ["000","001","010","011","100","101","110","111"]
= ["000","001","010","011"] ++ ["100","101","110","111"]
= (make ["00","01","10","11"] then add 0 to everyone) ++ (make ["00","01","10","11"] then add 1 to everyone)
= (binary 2 then add 0 to everyone) ++ (binary 2 then add 1 to everyone)
3 Likes