stuff & things

More F# thoughts

It’s pretty irritating so far, but I can’t tell if that’s because I don’t know what I’m doing or because I don’t have some key insight into the language structure yet, or what. I find I’m poking around a lot trying to figure out if I need a terminator or a keyword in random places, and because of the structure of the language there’s not as many opportunities as in C# for the IDE to tell you what to type next.

There’s also the #light thing which is silly. The option should clearly have been #dark (or whatever the opposite of #light is in this case) or a command line option to make it compatible with whatever Caml dialect is non-#light.

I feel like there’s things missing from Seq. and so on, but that’s more likely that I just don’t know what they’re called yet, or I’m expressing things incorrectly I’d guess. 

At the same time, it’s very pretty in a lot of ways. The interop with .net (though I haven’t used it yet), immumtability by default, FSI-in-VS, and multicore-niceness are obvious wins. I don’t know if it’s applicable to games yet: there’d be an inordinate amount of panic if extra computation was done unnecessarily of course. Anyway, I like it enough apparently, I just got Amazon to fire me a copy of “Expert F#”, which I hope is teh awesome.

Euler #3

The problem statement:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

The first thing we need to do likely is know if a number is prime:

let isprime x =
    x > 1 &&
    not(Seq.exists (fun n -> x % n = 0) {2..int(sqrt (float x))})

This is a little sneaky. First, it generates a list of numbers from 2 to the square root of the number to be tested (square root because the largest possible factor). Then, it uses an existence test to see if any of those numbers can divide into the candidate number. If they can, we know it’s not prime.

With that out of the way, we can attack the actual problem. My first attempt was very C-like, to whit:

let prob3 num = 
    for i = int(sqrt(float num)) to 2 do
        if num % int64 i = 0L && isprime(i) then return i
prob3 600851475143L

But, that doesn’t work. ‘return’ doesn’t exist, and the type of ‘for’ is unit, so there’s no way to get the result out. I was trying to avoid computing too many results, so going backwards was the goal (rather than making a list of answers and filtering them, as in the previous problems).

I didn’t exactly figure out how to do that, but I did come up with a reasonable solution (at least to my non-F# eyes):

let num = 600851475143L
{ for i in [2..int(sqrt(float num))] do
    if num % int64 i = 0L && isprime(i) then yield i }
|> Seq.fold(fun a x -> max a x) 0

First, we make a list of all the factors of the target number that are also prime (the comprehension). Then, fold the maximum value out of those. It’s definitely doing a lot more work than necessary, but it works OK.

There’s also a little bit of mucking around in this problem because the number was bigger than 2^32-1. F# handles it reasonably cleanly though, at least up to int64 range, by just adding some float/int/int64 calls to convert things to the right types explicitly. Not sure what bignum looks like yet though.

Euler Problem #2, redux

This is a similar attempt, not sure if it’s better or worse really, but uses comprehensions instead.

{ for i in [1..33] do
      let x = fib(i)
      if x < 4000000 && x % 2 = 0 then yield x }
|> Seq.sumByInt(fun x -> x)

Euler Problem #2

(only 191 problems to go, currently)

Problem #2 was stated as:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Pretty straightforward I guess.

let rec fib n =
    if n     else fib(n-1) + fib(n-2)

[1..40]
|> Seq.map(fib)
|> Seq.filter(fun x -> x < 4000000 && x % 2 = 0)
|> Seq.sumByInt(fun x -> x) 

I was wondering if the 4,000,000 was supposed to try to make me do something “smart” because it was intended to take a long time. But, I didn’t and it took about a second on my computer, even with the very dumb fib.

The weakest part is the “40”, but I feel like F# earned me that because after I typed in the definition of fib, I used the awesome FSI (interactive F# window in Visual Studio) to quickly test what numbers would make sure I got up to at least 4M (it was 33, but 40 seemed less sneaky).

There’s probably a better way to do the last line too, I guess fold over + would work. I was sort of hoping for a default Seq.sum without arguments, but I guess not. Maybe there’s a shorthand way of writing the identity function?

F# and Project Euler

I was vaguely looking for something that might make me smarter, wouldn’t be at all practical, and also wouldn’t be a huge time investment.

I started by working through the exercises of “Introduction to Algorithms” by C/L/R, but I didn’t make it too far. Maybe someday.

Project Euler is some math/algorithmic problems that seem to fit the bill. Since I was thinking I should learn an ML family language, I thought I’d try to solve them in F# and see how far I got.

Without further ado, here’s problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

and my probably not so amazing solution:

[1 .. 999]
|> Seq.sumByInt(fun x ->
    if x % 3 = 0 || x % 5 = 0 then x
    else 0) 

Not too hairy, but some neat bits:

|> is a pipelining operator that just changes the order of the arguments. Rather than nesting the [1..999] at the end, it goes at the beginning which makes more sense to read.

And, of course, first class functions.

I really hate “then” for whatever repressed-loathing-of-some-crappy-language-reason, but I’ll survive. I guess.

Where’s my monitoring?

Jenn and I were recently arguing about taking vitamin and other dietary supplements. Historically, I’d been rather dismissive towards them because they always felt very pseudo-scientific, but I’d never really thought about why it was that I felt that way.

Obviously it’s possible that they’re filling a very real need, particularly for people who have unusual diets (we’re vegetarian for example, which isn’t particularly unusual these days, but might be considered unusual on an evolved-from-monkeys-timescale). But (and it’s a big but), there’s really no practical way to know what effect of taking these things is. You could go for a weekly battery of blood/skin/whatever tests, but that’s both costly and time-consuming. Other than that, it falls to either correlation with secondary effects, or “how I feel” both of which are way too heavily influenced by other things going on in life and placebo effects.

Visiting any supplement or “natural”-something-or-other store reveals thousands of random options. The thing that really bothers me, is that if it they turn out not to be helping, at best you’re wasting a lot of money (if they’re doing nothing), but at worst, you could be creating health problems by ingesting mixes of things that really aren’t good for you.

So, getting to the point of all this, why can’t I monitor myself yet? I think this would pretty clearly be a game-changing startup: I stick my finger in a little machine before I get in the shower in the morning and it grabs some blood and skin (and maybe occasionally I give it some hair as a little treat). Then, it chugs away extracting as much useful information as is possible from the samples (lots and lots and lots of info in there!). Add a WiFi connection to it, and it doesn’t need any interface at all, just the ability to upload data to either a local machine, or preferably to a suitably encrypted and secured web site. The web site can give me a history of changes, monitor for flucuations, highlight defiencies (and maybe suggest supplements or diet modifications), or tell me that now would be a damn good idea to go see an MD or nutritionist. So, where the heck is my simple desktop monitoring system?

foo

Heard the new Foo Fighters on the radio (I assume the latest single), and all I could think was that if Kurt had heard it, he’d have shot himself in the face.

…

…

…

But hey, they won a Grammy or whatever. Maybe it’ll be for best Adult Contemporary next time. 

bash inputrc tab completion magic incantations

I can’t stand hitting TAB and having it do nothing because there’s two matches. Cycling seems vastly more useful to me. And, history-search (F8 in Windows), but both directions using PgUp/PgDown. I can never remember this magic so here it is for posterity (goes in ~/.inputrc):

TAB: menu-complete
"\e[Z": "\e-1\C-i"
"\e[5~": history-search-backward
"\e[6~": history-search-forward

Then, Tab and Shift-Tab cycle, and PgUp/PgDown cycle through history that matches. Much better! 

Emacs for Vim

I’m having a whack at trying to learn a reasonable amount of Emacs so I can attempt a project more reasonably in sbcl (and Weblocks). I’ve been programming in Vim for about 12 years and my brain/hands are very, very angry at this editor transgression.

Mostly because I know I’ll give up, and then try again much later, here’s some stuff that is permanently ingrained in my Vim brain that is the closest I could find in Emacs (so far at least). To be edited as I find more things. Vim on the left, Emacs on the right:

Movement 

• C-f, C-b = C-v, M-v
• hjkl = C-b, C-n, C-p, C-f
• HL (or ^$ for most people) = C-a, C-e
• wb = M-f, M-b
• O, o = ?  (C-o does some stupid thing)
• u, C-r = ?

Change/Deleting:

• das = ?
• cab = ?
• gqap = ?
• dd = ?

Clipboard:

• “+y = ?
• “+P = ?

The page movement commands are probably my biggest problem right now: for one they’re the dumb ones like Vim’s C-u/C-d that only move half a page (haven’t figured out how to make them only leave one line instead yet), and for two, it’s just kind of painful because you have to move your pinky and then repress the v, rather than just hold down control and toggle between f/b. Anyway, whatever. I’ll suck and use PgUp/PgDn for now.

No hjkl of course kills me, but everyone else too.

I keep hitting Esc when I’m done entering text so then the next Ctrl/Meta command doesn’t work because it’s been prefixed by an Escape. Ack. Pffft.

The most amusing thing so far is that I couldn’t figure out enough to edit my .emacs in Emacs so the first few edits were:

$ vim ~/.emacs

Hrm. 

JavaScript framework

I thought I liked jQuery, but it’s just a bit too weird after using it for a bit. I kept having the feeling that it was too much magic and not enough JavaScript. So, I’m using mootools now. It’s very similar, but one or both of the design and documentation is better, and as a result I’m much happier with it.