[SOLUTION][QUIZ] FizzBuzz (#126) [solution #1]

[MenTaLguY]

I've got two solutions this go-round. First, the solution I would present were I asked to do this in an actual job interview:

for n in 1..100
mult_3 = ( n % 3 ).zero?
mult_5 = ( n % 5 ).zero?
if mult_3 or mult_5
print "Fizz" if mult_3
print "Buzz" if mult_5
else
print n
end
puts
end

-mental

 

[MenTaLguY]

And, here's my second one, written in a subset of Ruby which corresponds
to a pure (though strict) lambda calculus, building up numbers, strings,
and everything else entirely from scratch. (Okay, I cheated a little
bit for actual IO)

Sadly Church numerals are very slow for non-tiny numbers, and Ruby
doesn't do tail recursion optimization which just makes matters worse.
But it does work, given enough time and stack space. Try running it and
see how high you can get!

-mental

alias LAMBDA lambda
def LAMBDA2(&f) ; LAMBDA { |x| LAMBDA { |y| f[x, y] } } ; end
def LAMBDA3(&f) ; LAMBDA { |x| LAMBDA { |y| LAMBDA { |z| f[x, y, z] } } } ; end

U = LAMBDA { |f| f[f] }

ID = LAMBDA { |x| x }
CONST = LAMBDA2 { |y, x| y }
FLIP = LAMBDA3 { |f,a,b| f[a] }
COMPOSE = LAMBDA3 { |f,g,x| f[g[x]] }

ZERO = CONST[ID]
SUCC = LAMBDA3 { |n,f,x| f[n[f][x]] }
ONE = SUCC[ZERO]
TWO = SUCC[ONE]
THREE = SUCC[TWO]
ADD = LAMBDA { |n| n[SUCC] }
FIVE = ADD[TWO][THREE]
SIX = ADD[THREE][THREE]
SEVEN = ADD[FIVE][TWO]
EIGHT = ADD[FIVE][THREE]
MULTIPLY = COMPOSE
FOUR = MULTIPLY[TWO][TWO]
NINE = MULTIPLY[THREE][THREE]
TEN = MULTIPLY[FIVE][TWO]
POWER = LAMBDA2 { |m, n| n[m] }
A_HUNDRED = POWER[TEN][TWO]

FALSE_ = ZERO
TRUE_ = CONST
NOT = FLIP
OR = LAMBDA2 { |m,n| m[m][n] }
AND = LAMBDA2 { |m,n| m[n][m] }

ZERO_P = LAMBDA { |n| n[CONST[FALSE_]][TRUE_] }

NIL_ = LAMBDA { |o| o[nil][TRUE_] }
CONS = LAMBDA2 { |h,t| LAMBDA { |o| o[LAMBDA { |g| g[h][t] }][FALSE_] } }
NULL_P = LAMBDA { |p| p[FALSE_] }
CAR = LAMBDA { |p| p[TRUE_][TRUE_] }
CDR = LAMBDA { |p| p[TRUE_][FALSE_] }
GUARD_NULL = LAMBDA3 { |d,f,l| NULL_P[l][CONST[d]][f][l] }
FOLDL = U[LAMBDA { |rec| LAMBDA3 { |f,s,l| GUARD_NULL[LAMBDA { |k| rec[rec][f][f[CAR[k]]][CDR[k]] }][l] } }]
DROP = LAMBDA { |n| n[GUARD_NULL[NIL_][CDR]] }
LENGTH = FOLDL[LAMBDA2 { |a, e| SUCC[a] }][ZERO]

MAKE_LIST = LAMBDA2 { |v,n| n[LAMBDA { |p| CONS[v][p] }][NIL_] }

LESSER_P = LAMBDA2 { |m,n| NOT[NULL_P[DROP[m][MAKE_LIST[ID][n]]]] }

DIVMOD_HELPER = U[LAMBDA { |rec| LAMBDA3 do |q,l,n|
NULL_P[l][CONST[CONS[q][ZERO]]][
LAMBDA2 do |r, t|
AND[NULL_P[t]][LESSER_P[r][n]][CONST[CONS[q][r]]][
rec[rec][SUCC[q]][t]
][n]
end[LENGTH[l]]
][DROP[n][l]]
end }]
DIVMOD = LAMBDA2 { |m,n| DIVMOD_HELPER[ZERO][MAKE_LIST[ID][m]][n] }

DIVISIBLE_BY_P = LAMBDA2 { |m,n| ZERO_P[CDR[DIVMOD[m][n]]] }

CHAR_0 = MULTIPLY[SIX][EIGHT]

FORMAT_NUM_HELPER = U[LAMBDA { |rec| LAMBDA2 do |s, n|
LAMBDA do |qr|
LAMBDA2 do |q, r|
ZERO_P[q][ID][FLIP[rec[rec]][q]][CONS[ADD[r][CHAR_0]]]
end[CAR[qr]][CDR[qr]]
end[DIVMOD[n][TEN]]
end }]

FORMAT_NUM = LAMBDA do |n|
ZERO_P[n][CONST[CONS[CHAR_0][NIL_]]][FORMAT_NUM_HELPER[NIL_]][n]
end

CHAR_F = MULTIPLY[SEVEN][TEN]
CHAR_i = ADD[A_HUNDRED][FIVE]
CHAR_z = ADD[A_HUNDRED][ADD[MULTIPLY[TWO][TEN]][TWO]]
CHAR_B = MULTIPLY[SIX][ADD[TEN][ONE]]
CHAR_u = ADD[A_HUNDRED][ADD[TEN][SEVEN]]

CHAR_NEWLINE = TEN

FIZZ = CONS[CHAR_F][CONS[CHAR_i][CONS[CHAR_z][CONS[CHAR_z][NIL_]]]]
BUZZ = CONS[CHAR_B][CONS[CHAR_u][CONS[CHAR_z][CONS[CHAR_z][NIL_]]]]

OUTPUT_STRING = LAMBDA do |s|
print FOLDL[LAMBDA2 { |a,e| a << e }][[]].map { |i| i[LAMBDA { |s| s + 1 }][0] }.pack("C*")
end

SEQUENCE = FLIP[COMPOSE]

FIZZBUZZ_HELPER = U[LAMBDA { |rec| LAMBDA2 do |i,r|
NULL_P[r][ID][LAMBDA do
LAMBDA2 do |mult_3, mult_5|
SEQUENCE[
SEQUENCE[
OR[mult_3][mult_5][
SEQUENCE[
mult_3[LAMBDA { OUTPUT_STRING[FIZZ] }][ID]
][
mult_5[LAMBDA { OUTPUT_STRING[BUZZ] }][ID]
]
][LAMBDA { OUTPUT_STRING[FORMAT_NUM] }]
][
LAMBDA { OUTPUT_STRING[CONS[CHAR_NEWLINE][NIL_]] }
]
][
LAMBDA { rec[rec][SUCC][CDR[r]] }
][nil]
end[DIVISIBLE_BY_P[THREE]][DIVISIBLE_BY_P[FIVE]]
end][nil]
end }]

FIZZBUZZ = LAMBDA do |c|
FIZZBUZZ_HELPER[ONE][MAKE_LIST[ID][c]]
end

FIZZBUZZ[A_HUNDRED]

 

[Joel VanderWerf]

And, here's my second one, written in a subset of Ruby which corresponds
to a pure (though strict) lambda calculus, building up numbers, strings,
and everything else entirely from scratch. (Okay, I cheated a little
bit for actual IO)

Sadly Church numerals are very slow for non-tiny numbers, and Ruby
doesn't do tail recursion optimization which just makes matters worse.
But it does work, given enough time and stack space. Try running it and
see how high you can get!

Ok, you're hired. Your first project is to write a web server in Malbolge.

 

[MenTaLguY]

--=-CDSr6rtc6gt2MoSqYcIb
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

Incidentally, this second solution could probably be made to run in a
reasonable time if the mod-15 pattern in the output were exploited. But
I'm lambda'd out at the moment, so it will remain an exercise for the
reader.

-mental

--=-CDSr6rtc6gt2MoSqYcIb
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)

iD8DBQBGZimbSuZBmZzm14ERAkRJAKDCEMBIIo2JN6MwZyYtFbNhKWVmZQCgtNT6
xMuk4StpuXruofgxo2OmZyg=
=qLIF
-----END PGP SIGNATURE-----

--=-CDSr6rtc6gt2MoSqYcIb--

 

[James Edward Gray II]

And, here's my second one, written in a subset of Ruby which
corresponds to a pure (though strict) lambda calculus, building up
numbers, strings, and everything else entirely from scratch.
(Okay, I cheated a little bit for actual IO)

That is wild.

I'm just staring at the code. I know enlightenment is hidden in
there somewhere...

James Edward Gray II

 

[Brad Phelan]

And, here's my second one, written in a subset of Ruby which corresponds
to a pure (though strict) lambda calculus, building up numbers, strings,
and everything else entirely from scratch. (Okay, I cheated a little
bit for actual IO)

Sadly Church numerals are very slow for non-tiny numbers, and Ruby
doesn't do tail recursion optimization which just makes matters worse.
But it does work, given enough time and stack space. Try running it and
see how high you can get!

I thought it was randomly generated joke code jibberish till I copied
and ran it and it worked .. slowly. So I started revising my lambda
calculus till my brain hurt... So I ask a question...

Using your Ruby Church numerals is it possible to test for equality?
Perhapps you are doing it but I was unable to parse the
whole algorithm out and figure out exactly what all the lambdas
you use do.

Cheers

Brad

 

[MenTaLguY]

--=-jTvpSXKJkl41Tfq3wU9t
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

Using your Ruby Church numerals is it possible to test for equality?=20

Sure!

EQUAL_P =3D LAMBDA2 { |m,n| NOT[OR[LESSER_P[m][n]][LESSER_P[n][m]]] }

-mental

--=-jTvpSXKJkl41Tfq3wU9t
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)

iD8DBQBGZ2yiSuZBmZzm14ERAoihAKCHqbO946qw6jrjFAyAS0uVbw8yxQCePr67
TAHDqrtESdJh/r+Kgi6hLjM=
=BMRu
-----END PGP SIGNATURE-----

--=-jTvpSXKJkl41Tfq3wU9t--

 

[MenTaLguY]

--=-fQeRyKvHwV87qm/WDkXj
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

Perhapps you are doing it but I was unable to parse the
whole algorithm out and figure out exactly what all the lambdas
you use do.

If it helps, what a lot of the math stuff does is create lists of the
length specified by a number, manipulate those, and then count their
lengths to get back to a number. For instance, subtraction would be:

SUBTRACT =3D LAMBDA2 { |m,n| LENGTH[DROP[n][MAKE_LIST[ID][m]]] }

(here, ID is just used as a dummy value to populate the list with)

-mental

--=-fQeRyKvHwV87qm/WDkXj
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)

iD8DBQBGZ4rLSuZBmZzm14ERApC/AJ4v49mNvUhEl2sD/1NOFE1m5a1qVACgue23
XJyADigFwFzb6a1CNXN5Vi0=
=+8jj
-----END PGP SIGNATURE-----

--=-fQeRyKvHwV87qm/WDkXj--

 

[Robert Dober]

Perhapps you are doing it but I was unable to parse the
whole algorithm out and figure out exactly what all the lambdas
you use do.

If it helps, what a lot of the math stuff does is create lists of the
length specified by a number, manipulate those, and then count their
lengths to get back to a number. For instance, subtraction would be:

SUBTRACT = LAMBDA2 { |m,n| LENGTH[DROP[n][MAKE_LIST[ID][m]]] }

must work nicely for n>m
But interesting stuff.

Cheers
Robert

 

[Brad Phelan]

Perhapps you are doing it but I was unable to parse the
whole algorithm out and figure out exactly what all the lambdas
you use do.

If it helps, what a lot of the math stuff does is create lists of the
length specified by a number, manipulate those, and then count their
lengths to get back to a number. For instance, subtraction would be:

SUBTRACT = LAMBDA2 { |m,n| LENGTH[DROP[n][MAKE_LIST[ID][m]]] }

(here, ID is just used as a dummy value to populate the list with)

-mental

Thanks for the pointers. I don't have too much time today to think about
this ( public holiday and I'm going out in the sun ) but I know when
I do I'll want to know the concept here behind lists. Are they real
lists as in Ruby Array which I doubt or abstract concepts like
the Church Numerals.

I'll take a look Monday and see if I can understand more.

Regards

Brad

 

[MenTaLguY]

SUBTRACT = LAMBDA2 { |m,n| LENGTH[DROP[n][MAKE_LIST[ID][m]]] }

must work nicely for n>m

Church numerals correspond to the natural numbers, so negative results aren't possible. For n>m, I could either let the computation diverge or return ZERO -- I opted to return ZERO.

It is possible to build a representation of general integers atop Church numerals (one obvious way would be to use a pair consisting of a sign flag and a magnitude), but that was more than I needed for this particular problem.

-mental

 

[MenTaLguY]

Thanks for the pointers. I don't have too much time today to think about
this ( public holiday and I'm going out in the sun ) but I know when
I do I'll want to know the concept here behind lists.

Lists are linked lists made of pairs, as in Lisp. Since we chose to represent true and false as two-argument functions which return their first or second argument, respectively, we can take advantage of this to describe a pair as a function which takes true or false as an argument to select an element of the pair.

Such a pair can be created by a function like:

MAKE_PAIR = LAMBDA2 { |first, second| LAMBDA { |which| which[first][second] } }

And functions for extracting the first or second value from a pair constructed by MAKE_PAIR can be written like this:

FIRST = LAMBDA { |pair| pair[TRUE_] }
SECOND = LAMBDA { |pair| pair[FALSE_] }

My definitions for CONS, CAR, and CDR in fizzbuzz were a little more involved, because I also needed to be able to represent an empty list (and test for it). So, what I did is roughly equivalent to:

NIL_ = MAKE_PAIR[nil][TRUE_]
CONS = LAMBDA2 { |head, tail| MAKE_PAIR[MAKE_PAIR[head, tail]][FALSE_] }
CAR = LAMBDA { |cell| FIRST[FIRST[cell]] }
CDR = LAMBDA { |cell| SECOND[FIRST[cell]] }
NULL_P = LAMBDA { |cell| SECOND[cell] }

A tagged data structure, basically, with a flag indicating whether a cell is a null list or not.

-mental

 

[MenTaLguY]

Are they real lists as in Ruby Array which I doubt or abstract concepts like
the Church Numerals.

In some sense, these things are only as abstract as you want them to be. Instead of implementing Church numerals like this (expanded a bit for clarity):

ZERO = LAMBDA2 { |f,x| x }
ONE = LAMBDA2 { |f,x| f[x] }
SUCC = LAMBDA { |n| LAMBDA2 { |f,x| f[n[f][x]] } }
ADD = LAMBDA2 { |m,n| m[SUCC][n] }
MULTIPLY = LAMBDA2 { |m,n| LAMBDA2 { |f,x| m[n[f]][x] } }
POWER = LAMBDA2 { |m,n| n[m] }

I could also have done something like this:

class ChurchNumeral
attr_reader :value

def initialize(value)
@value = value
end

def call(f)
LAMBDA { |x| @value.times { x = f[x] } ; x }
end
alias [] call
end

ZERO = ChurchNumeral.new 0
ONE = ChurchNumeral.new 1
SUCC = LAMBDA do |n|
if ChurchNumeral === n
ChurchNumeral.new n.value + 1
else
LAMBDA2 { |f,x| f[n[f][x]] }
end
end
ADD = LAMBDA2 do |m,n|
if ChurchNumeral === m and ChurchNumeral === n
ChurchNumeral.new m.value + n.value
else
m[SUCC][n]
end
end
MULTIPLY = LAMBDA2 do |m,n|
if ChurchNumeral === m and ChurchNumeral === n
ChurchNumeral.new m.value * n.value
else
LAMBDA2 { |f,x| m[n[f]][x] }
end
end
POWER = LAMBDA2 do |m,n|
if ChurchNumeral === m and ChurchNumeral === n
ChurchNumeral.new m.value ** n.value
else
n[m]
end
end

As described in my previous email, I did take the former sort of approach for lists though.

-mental