HN Explorer

40 comments

[ 2.9 ms ] story [ 93.4 ms ] thread
jdn
It's quite amusing how accurate this is, knowing Haskell users across a number of these levels. It's quite a handy learning tool as well with the added explanations at the bottom.
wslh
It misses the math Haskell programmer using the closed form expression: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...

What is the best way to implement it in Haskell since Phi and Psi are real numbers?

Edit: as the user tome told me.... It was about the factorial function not about fibonacci. I blindly see fibonacci.

freyrs3
Naive implementation might be:

  fib :: Integer -> Integer
  fib x = truncate $ ( 1 / sqrt 5 ) * ( phi ^ x - psi ^ x )
  	where
  	    phi = ( 1 + sqrt 5 ) / 2
  	    psi = ( 1 - sqrt 5 ) / 2
fhars
Alas, that version is only correct up to x = 25, because

    *Main> 1 / sqrt 5 * (((1 + sqrt 5) / 2) ^ 26 - ((1 - sqrt 5) / 2) ^ 26)
    121392.99999999999
happens to be just on the wrong side of the truncate.
tome
That's not a Haskell question per se, but in any language you can implement it using two intergers (a, b) that represent the number a + b * sqrt(5).
wslh
Yes, it is a Haskell question more than you think ;-) since, for example, using types for fraction or other kind of patterns can work different in Haskell than in other languages. I think it's possible in Haskell to add symbolic manipulation as well like in http://christopherolah.wordpress.com/2012/06/01/hasksymb-an-... or http://homepages.inf.ed.ac.uk/wadler/realworld/docon2.html

Also, there are implementations in the list that can be implemented in the same way on non functional languages.

tome
I think it would be neater doing it in Haskell than, say Java, but the fundamental idea would be the same in both.
FreeFull
But this is all about the factorial function, not the fibonacci sequence
wslh
It is the close form of the fibonacci function.
tome
But the original post is about factorial, which has nothing to do with fibonacci!
wslh
Oooooops! You caught me. I didn't pass the Turing Test today! >:O
lelf
For example like this (it provides exact result Edit—no matter how big n is). CReal is some magic.

  import Data.Number.CReal

  fib :: Integer -> Integer
  fib n = round $ (φ^^n - (-φ)^^(-n)) / sqrt 5
      where
        φ = (1 + sqrt 5) / 2 :: CReal


  -- While we at it
  fib' n = fibs !! n
      where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
carterschonwald
Yeah, the constructive reals lib is really cool, and that's definitely an example where it really shines.
Peaker
Another one:

  fibs = map fst (iterate (\(cur,next)->(next,cur+next)) (0,1))
wging
It does miss a trivial optimization. For example,

    fac n = product [1..n]
can be replaced with

    fac n = product [2..n]
and will still do the right thing for n == 0, n == 1. Saves you a multiplication!
lelf
You are right! But let's do it the proper way

  {-# RULES
    "product/1" forall x. product [1..x] = product [2..x]
    #-}

  fac n = product [1..n]
jfarmer
Although the original post wasn't about it, here's a version of exact arithmetic in the field extension containing phi.

I wrote in Ruby a long time ago: https://gist.github.com/jfarmer/82500f2b52c540df5fbc

You still have to implement the exponentiation algorithm, so you're never really going to get O(1). This is better than O(n), though.

With those things implemented it becomes

  def fib_phi(n)
    ((PhiRational.new(0,1)**n - PhiRational.new(1,-1)**n)/PhiRational.new(-1, 2)).a.to_i
  end
which is the explicit formula. I'd love to see the same thing in Haskell, which I imagine would look less crazy.
nandemo
Understandable mistake, since fibonacci is the helloworld of functional programming.

You might want to suggest something with the Sterling formula instead, but that would be trickier (it's an approximation, not an exact formula).

wreckimnaked
I really want to understand about morphisms and category theory after reading this. Can anyone point out any good introduction to the category theory behind those catamorphisms?
sfvisser
More of a programming than a CT introduction, but very useful nonetheless: Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (1991), by Erik Meijer, Maarten Fokkinga, Ross Paterson
davidp
I am simultaneously intrigued by the possibilities of functional programming, and horrified by the ways it can take people off into the weeds.

Were I to use Haskell in a real-world project with teammates, I'd have to keep an iron grip on the complexity of the code the team writes. Maintainability (mainly readability/comprehensibility as far as I'm concerned) is far more important for the kind of work I do than theoretical purity and hypothetical applicability to classes of problems the team isn't facing.

I could easily keep things on the rails on my own, but I suppose it's simply unsettling thinking about using Haskell for something sizable; probably due to my own lack of experience with it. I'd love to hear about sizable real-world Haskell projects, since I think FP is the future of software engineering.

mwcampbell
Your concerns resonate with me. I think in most cases, particularly in commercial software development, we should value clarity, familiarity, and maintainability over cleverness, expressiveness, and terseness.

I think that like Haskell, Scala's flexibility tends to take some people off into the weeds. See, for example, Coda Hale's concerns about using Scala at Yammer, from about 2 years ago:

http://codahale.com/downloads/email-to-donald.txt

However, I think we need to be careful not to overvalue familiarity. Rich Hickey's talk "Simple Made Easy" is well-known, and I think he's correct to tell us that we should value simplicity over ease. I guess the answer is to use functional programming to make our software simpler, and not let cleverness take us off into the weeds.

hiker
This is a Haskell insider-joke. As is the The International Obfuscated C Code Contest. You wouldn't judge the value of the C language for writing, let's say, a unix kernel based on the code from IOCCC, would you?

Don't take it so seriously.

coolsunglasses
Clojure has worked wondrously for myself and my colleagues in terms of clean, nice idiomatic code that doesn't require a bunch of marshalling code standards together.
jeremiep
You can probably find as many ways to write an algorithm in most languages. At least here the different versions vary in length by at most one page ;)
6ren
FP is the future of software engineering, and always will be.
cgag
Isn't maintainability going to be significantly added by so much being statically checked? Even if people are writing functions that are internally ugly, wouldn't haskell largely enforce that those functions can't really hurt the outside world?

It seems to me like "off the rails" in a pure language is going to be much nicer than off the rails in a language where mutable state is the norm.

nikatwork
I used to think this about Java's static typing. Then I worked on a ten person team writing a SAAS project, which had some... less than stellar coders. They would write 800 line functions, complete with 15 levels of nested "if else" statements and two-letter variable names.

Yes their code sorta worked, but Deity help you when it came time to add a feature or fix a bug.

Contrawise, my next project was with a team of moderately competent Perl programmers. Functions were concise and variable names reasonably clear. Maintenance was a breeze by comparison.

cgag
People who are going to use bad variable names and 800 line functions are probably not even worth thinking about, but if you had a bunch of mediocre programmers working in each language (perl, java, haskell), do you think their code would be more maintainable as you moved up the level of static typing? I would think so, but I don't have any actual experience with this or a really strong opinion on the subject.
nikatwork
My point is that architecture and programmer ability is a much stronger influence on maintainability than type system IME. Although your experiment would be an interesting one.

Java's static typing did make it easier to traverse the code using an IDE, and avoided the occasional subtle type casting bug. The easy integrated debugging was nice too (eg setting remote breakpoints).

These benefits were vastly offset by the productivity hit from wading through boilerplate code, language verbosity and dealing with type conversion issues.

tome
> Isn't maintainability going to be significantly added by so much being statically checked? Even if people are writing functions that are internally ugly, wouldn't haskell largely enforce that those functions can't really hurt the outside world?

Yes and yes (in my experience).

ExpiredLink
Haskell? Just let it fade away!
Peaker
Ironically, Haskell is gaining traction while your comment is fading away :-)