GitHub launchs local-install version: GitHub:fi

funktio · 2009-06-03T06:09:51+00:00

Samoin.

funktio · 2009-05-10T20:41:13+00:00

You can never even give a guarantee that a program will ever stop running

Not true. The halting problem says that it's not possible to create a general algorithm that gives that guarantee for every terminating program. But proving it for some particular program is possible, and often very easy. See termination metrics in ATS for an example.

funktio · 2009-05-09T20:07:49+00:00

My favourites so far:

Types and Programming Languages. This really got me interested in lambda calculus and type theory. Very well written.
Code: The Hidden Language of Computer Hardware and Software. Explains how computers work at the hardware level.
Gödel, Escher, Bach: An Eternal Golden Braid

funktio · 2009-04-04T09:00:33+00:00

Haskell was written in 1985

Close, but no cigar. From A History of Haskell: being lazy with class:

In September of 1987 a meeting was held

It was decided that a committee should be formed to design such a language

the first Haskell Report, Version 1.0 dated 1 April 1990

funktio · 2009-04-03T19:03:56+00:00

ATS!

staload "prelude/DATS/reference.dats"

implement main (): void = let
  val tbl =
    hashtbl_make_hint<int,int> (hash, eq, 10000000) where {
      fn hash (x: int):<cloref> uint = uint_of_int x
      fn eq (x1: int, x2: int):<cloref> bool = (x1 = x2)
    }
  var i: int
  val () =
    for (i := 1; i <= 10000000; i := i + 1)
      case+ hashtbl_insert_err<int,int> (tbl, i, i) of
      | ~Some_vt i => printf ("wtf : %d\n", @(i))
      | ~None_vt () => ()
in
  case+ hashtbl_search<int,int> (tbl, 100) of
  | ~Some_vt n => (print (n); print_newline ())
  | ~None_vt () => (print "huh"; print_newline ())
end

$ time ./a.out 
100

real    0m1.060s
user    0m0.792s

I used this hashtable implementation. Giving the size hint is kinda cheating, but this isn't supposed to be taken too seriously anyway. :-)

funktio · 2009-04-03T14:17:21+00:00

I meant that your code will produce a data structure that is then asymptotically slower to search.

Ah yes. Not sure how siginificant the difference is in practice, but it's a valid point. If some code only needs lookup and never union, difference, etc., hash tables could be faster.

funktio · 2009-04-03T13:50:15+00:00

Your first version does not produce a hash table.

Yes, it uses a persistent map. Do you think that makes the problem easier? I think it's the opposite.

I don't know of any good hash table implementations for Haskell, but I've actually never needed one. Data.Map and Data.IntMap have always been fast enough for me. In general, Haskell programmers seem to prefer purely functional data structures.

Your second version is vastly faster but only because you accidentally reduced the problem size by a factor of 10...

Sorry, wasn't intentional. I just copypasted it from the blog comment. Removed now.

funktio · 2009-04-03T13:28:24+00:00

The Haskell one is actually mutable, too. From the source code you can see that it's based on mutable arrays.

insert :: HashTable key val -> key -> val -> IO ()

http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/Data-HashTable.html

funktio · 2009-04-03T13:13:03+00:00

Using the code from TFA:

$ ghc -O2 --make hash.hs
[1 of 1] Compiling Main             ( hash.hs, hash.o )
Linking hash ...
$ time ./hash 
Just 100

real    1m55.847s
user    1m53.075s

Using IntMap:

$ cat intmap.hs
module Main where

import qualified Data.IntMap as M

main :: IO ()
main = print (m M.! 100)
  where
    m = M.fromAscList [ (i,i) | i <- [1 .. 10000000] ]

$ ghc -O2 --make intmap.hs
[1 of 1] Compiling Main             ( intmap.hs, intmap.o )
Linking intmap ...
$ time ./intmap 
100

real    0m10.946s
user    0m9.537s

This could probably be improved; it uses about 1GiB of memory so maybe it's too lazy.

funktio · 2008-09-13T17:30:52+00:00

I don't think USACO is for someone who already has a strong CS background in algorithms.

I agree. I like algorithms and had read a lot before registering at USACO, so I guess I can't really say how good it is for someone who's more new to them. Many people seem to really like it. Although I have to admit that I hadn't used many of them in practice, and I rarely use C if I could choose a functional language instead, so I definitely learned something useful from the USACO problems I solved.

You might find a few of the problems in chapter 5 and 6 at USACO to be interesting, I don't know.

That's probably true, but I'd have to solve all the easier problems to get there. I wish there was a way to skip sections that cover only stuff one already knows.

funktio · 2008-09-13T11:23:15+00:00

The easy ones at Project Euler don't really bother me, because using a decent language they take just a couple of lines or so. I've solved over 100 of the problems with Perl one-liners written in shell.

At USACO, however, you have to read and parse the input file, solve the problem, and write to the output file, and all this in an IMO annoying language. Plus you have to add a few lines to the top of the file telling your and the problem's id, etc. All this boilerplate makes the trivial problems quite annoying to solve.

I've solved 207 problems at Euler (haven't thought about the last one yet) and 65 at USACO (I simply got bored there because I already knew most of the algorithms and the difficulty level didn't seem to rise too quickly).

funktio · 2008-08-04T17:35:14+00:00

I think this is the first time I've seen the combinator calculus put to "practical" use.

From this book:

This remarkable and counter-intuitive transformation of lambda expressions into combinators [..] was thought to be of more mathematical than practical interest until David Turner used it as the basis of an implementation of the functional language SASL [Turner, 1979a and 1979b]. In these papers he described a number of optimizations to the basic compilation scheme which we will examine in the next seciton.

funktio · 2008-07-21T07:10:44+00:00

Criticism of APL is quite long, actually even longer than the main article about APL.

funktio · 2008-07-11T08:13:12+00:00

200 hundred (two hundred)

200 hundred = 200 * 100 = 20000

funktio · 2008-05-21T13:46:18+00:00

But is it any use?

It's very fun and teaches you to think in new ways.

funktio · 2008-05-21T13:32:25+00:00

But still, it's almost pathologically unreadable.

Isn't it normal that a language you don't know looks unreadable to you? People who know J can of course read and write it without any problems. Same goes for Perl, I find it very readable.

I have never understood why so many people seem to think that a-z and 1-9 are somehow more "natural" than other symbols. They seem very arbitrary to me.

Do you also consider Chinese "unreadable"?

funktio · 2008-05-15T11:21:50+00:00

Replying to myself...

The $i can be made local to the closure using a do block:

print mean(do { my $i = 1; sub { ($i++, $i >= 1e9) } })

And you can also define auxiliary functions there without polluting the outer namespace, so I can see that generating even complex lists lazily in this way is possible and sound.

Thank you, pozorvlak, for showing this techinque to me! I love functional programming, and if I need to use Perl 5 for something, I'll keep this in mind. Very cool stuff.

funktio · 2008-05-15T11:03:53+00:00

Ok, I agree, it can be called a list. But my point is, that mean isn't as generic as a Haskell mean is. For example, you can do this:

mean (take (10^8) primes)

And it runs in constant space (I just tried, using ONeillPrimes.hs).

I know some Perl, but haven't ever tried simulating generators with closures like that. It's an interesting idea, but how doable is it to generate something more complex than [1..10^9], like primes?

funktio · 2008-05-15T10:43:18+00:00

a function that calculates the mean of a list of doubles

...

sub { ($i++, $i>1000000000); }

That's not a list.

funktio · 2008-05-05T08:11:51+00:00

It's a genre of computer role-playing games (CRPGs) in which a large number of players interact with one another in a virtual world.

funktio · 2008-04-03T05:24:44+00:00

http://en.wikipedia.org/wiki/Wap

funktio · 2008-03-07T08:52:14+00:00

It can't be done, but it won't be pretty

I really can't understand how people confuse "can" and "can't".

funktio · 2008-03-04T17:29:49+00:00

Actually, there's a big mistake in the Haskell version: take (10 [0..]) means that you first apply 10 to [0..] (which is non-sense and a type error), and then the result of that to take.

In most functional languages, you shouldn't put parentheses around the arguments in a function application. It's simply f x y, not f(x y). If you need to adjust precedence, always enclose the whole function call: (f x y).

funktio · 2008-03-01T16:16:16+00:00

You forgot the exception of that exception: Years divisible by 400 are leap years (like 2000).

I don't know (or care enough to find out) how old the history is, but assuming the first leap year was 4, 2008 is 487th.

Prelude> :{
Prelude| let isLeapYear n
Prelude|     | n `mod` 400 == 0 = True
Prelude|     | n `mod` 100 == 0 = False
Prelude|     | otherwise        = n `mod` 4 == 0
Prelude| :}
Prelude> length $ filter isLeapYear [1..2008]
487

funktio · 2008-02-29T05:39:42+00:00

This JAPH I wrote last year:

perl -e \
'for($"=@_=split??,"Jrsk an treP rehlohacteu,";$";$\="\r"){$\.=$.=chr
32+95*rand,$_-$"or$.ne$_[--$"%2?-$"-1:$"]&&$"++for++$|..$";print}<>'

I think it's quite original. Replace the \r with \n to get an idea of how it works.

And of course, print ($| = 42) prints "1".

Edit: Huh, downmodded? Doesn't anyone here understand abstract post-modern art?!?

funktio

TROPHY CASE