Thursday, July 15, 2010

The shortest oneline brainf*ck interpreter in python (558 characters)

Hi, it is Dr. NISHIO Hirokazu. This code was written in 2006-09 but I didn't have publish yet in English.

get from here: http://gist.github.com/476940. It takes a filename as an argument and exec it as Brainf*ck code. All illegal characters are ignored.

exec(reduce(lambda x,y:x.replace(y[0],y[1:]),'Iz"d",|Jz"t",|K1),"|L.read(|Mimport |O,lambda|Psys.std|Q",0);z"|R"Yzp,|S}.get(code[|T)or |U"YZor z"p",p|Vifilter(bool,(|W)%256)or Z,"|X)for x in count())).next()|Y:lambda:|Zz"c",c+1)|q(globals().get(p,0)|zglobals().__setitem__('.split('|'),'Msys;from itertools Mcount,ifilter;z"cQpQj"O kYq==0)^(k==-1)and(Jc+kTI1TVId+{"]":-1,"[":1St],0)*kTd==0 or Jt+kXand z"c",t+1T1TZ);z"code",file(sys.argv[1])L));Vc==len(code)or({">U+K<U-K+Rq+1W-Rq+255W."YPout.write(chrq)TZ,",Rord(PinL1)W[":j(K]":j(-1),Sc]O:Z)()and NoneX'))

See this charm point!

>U+K<U-K+Rq+1W-Rq+255W

It's a definition of >, <, + and - !

Monday, July 12, 2010

Haskell Quiz Answer

Hi, it is Dr. NISHIO Hirokazu. This is an answer for Haskell Quiz. Please read it in advance.

Why some program show strange behavior? To answer the question, I should define what is "strange". For example the following behavior is strange.


// JS
var a = ***, b = ***, c = ***;
console.log(a < b); // true
console.log(b < c); // true
console.log(c < a); // true


In the case, "strange" means "different from mathematical behavior". Now the answer is clear, it is because those are not purely mathematical objects.


var a = "9", b = 10, c = "100";
console.log(a < b); // true
console.log(b < c); // true
console.log(c < a); // true


Haskell also shares some common "strangeness" with other languages.

Prelude> let x = *****
Prelude> x == x + 1
True

You may know the quiz in the other language. This "strangeness" come from the limited resolution of floating point number.

Prelude> let x = 2 ** 64
Prelude> x == x + 1
True


Now, return to the problem I posted.

In Haskell, you can overload different value on one name.
You may disagree. You may see "Multiple declarations of something" error.
But wait. Didn't you have ever defined 'show'? Isn't it overloaded?

Haskell is very different from C++/Java. In C++/Java, you can overload functions whose type of arguments are different. In Haskell, you can also overload functions whose type of return value are different. It is very important.

The quiz's tricks are,

  1. You can overload in Haskell
  2. You can overload functions whose return value are different
  3. and there are no need to take argument
  4. (+) and (==) are t -> t -> t, so it can be used to restrict arguments' type. x + (1::Int) says x is (x::Int).
  5. Number Literal (e.g. 0) are (Num a) => a, so it can be used as both (0::Int) and (0::Integer).


Now let me show my answer.


class Foo t where
a :: t
b :: t

instance Foo Int where
a = 0
b = 1

instance Foo Integer where
a = 1
b = 0

c :: Int
c = 0

d :: Integer
d = 0

main = do
print $ a + c == 0 -- True.
print $ a == c -- True. a::Int == c::Int == 0.
print $ c == 0 -- True.
print $ a + d == 1 -- True.
-- d is Integer. So the variable a is a::Integer,
-- which equals 1. "d == 1" is a misconception.
print $ b + c == 1 -- True. b::Int is 1.
print $ b + d == 0 -- True. However, b::Integer is 0.
print $ b == d -- True. Yes, both are 0::Integer;
print $ d == 0 -- True.
-- Why I use "d == 0" not "b == 0"?
-- Because it causes "ambiguous type" error.
-- You know, ":t 0" is "(Num t) => t". No way to determine
-- it is Int or Integer.

-- hints to make answer unique (perhaps...)
print $ sum([a, b, c]) -- 1: It is [0, 1, 0]::[Int]
print $ sum([a, b, d]) -- 1: It is [1, 0, 0]::[Integer]
print $ [a, b, c] !! a -- 0: (!!) take Int argument,
print $ [a, b, c] !! b -- 1: so it says (a::Int /= b::Int)
print $ [a, b, c] !! c -- 0
-- Why I didn't show [a, b, c] !! d is,
-- it causes error because d is Integer.

Friday, July 2, 2010

Real Point-free Haskell Program

Hi, it is NISHIO Hirokazu. I'm trying to make *REAL* point-free Haskell program. In other words, I want to make point-free (arguments-less) Haskell code with any point(.)

You may know, usually most of Haskell programmer use (.) operator to combine functions. However, it is not necessary. It can replace with (<*>) and const.


Prelude Control.Applicative> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
Prelude Control.Applicative> :t \x y z -> (const x <*> y) z
\x y z -> (const x <*> y) z :: (a -> b) -> (b1 -> a) -> b1 -> b


So anytime you want to use (.) operator, you can do it without (.)


Prelude Control.Applicative> (map . (+)) 1 [1, 2, 3]
[2,3,4]
Prelude Control.Applicative> (const map <*> (+)) 1 [1, 2, 3]
[2,3,4]


And it is also easy to remove points from float expression:


Prelude> 1.5
1.5
Prelude> 15e-1
1.5


The most biggest problem is how to remove this point.

import Control.Applicative
^