# Is there a better solution to this Fibonacci implementation in Go?

At the end of the Day 1 Go Course slides (pdf) there is an exercise stated as follows (NOTE: the course in the linked presentation is considered obsolete. If you are looking to learn Go the suggested route is first via http://tour.golang.org):

You all know what the Fibonacci series is. Write a package to implement it. There should be a function to get the next value. (You don't have structs yet; can you find a way to save state without globals?) But instead of addition, make the operation settable by a function provided by the user. Integers? Floats? Strings? Up to you.

How does the following solution rate with respect to its 'Go'-iness?

package fib

type BinOp func (uint64, uint64) uint64

func fib_intern(a, b uint64, op BinOp) uint64 {
Fib = func(opnew BinOp) uint64 {
return fib_intern(b, op(a,b), opnew)
}
return a
}

var Fib = func(op BinOp) uint64 {
return fib_intern(0,1,op)
}


Which can then be called like:

package main

import (
"./fib"
"fmt"
)

func add(a, b uint64) uint64 {
return a+b
}

func main() {
for i := 0; i < 20; i++ {
}
}

-
Probably the wrong place to ask. Try asking on StackOverflow. –  Loki Astari Sep 16 '11 at 14:46
OK, happy for it to be migrated if its more suitable over in StackOverflow. –  Anthony Cramp Sep 16 '11 at 23:29
I don't know, it seems to meet the criteria for here. Biggest problem currently is that the link is dead. Presumably the course is obsolete and has been removed from the Go site. –  Sonia Feb 3 '13 at 18:45
Thanks for pointing out the broken link. I've updated it to point to an archived version of the course. However, you are correct in that the content is now considered obsolete and the recommended starting point is the Go Tour (tour.golang.org). –  Anthony Cramp Feb 24 '13 at 12:28

The link is dead and the code doesn't compile, but there is still an obvious issue to critique: Part of the challenge was to not save state with "global variables." In Go, package variables of the package main are typically considered "global variables". However, only a single instance of any package ever exists at run time, so package variables of all packages are essentially global variables as well. The code here uses a package variable fib.Fib, thus the code is failing the exercise from the start, working or not.

Edit: Thank you Anthony for tracking down the archived course and updating the question. It helps to have the full context. It also helps to have code working with a current version of Go, which is pretty easy:

package fib

type BinOp func(uint64, uint64) uint64

var Fib func(op BinOp) uint64

func init() {
Fib = func(op BinOp) uint64 {
return fib_intern(0, 1, op)
}
}

func fib_intern(a, b uint64, op BinOp) uint64 {
Fib = func(opnew BinOp) uint64 {
return fib_intern(b, op(a, b), opnew)
}
return a
}


Go now has stricter checking of static dependencies and reports "initialization loop" with the old code. My update of your code works by moving the initial assignment of Fib to an init function, which runs at program startup.

I'll abandon this answer now and add another answer where I try to stick to your request for a review of the 'Go'-iness.

-
Thanks for the code correction. –  Anthony Cramp Mar 6 '13 at 11:02

With working code it's fun to instrument it and watch it work. Each call to fib.Fib computes a new value in the sequence and also replaces itself with a new function literal to hold the new vaue. It's computationally efficient but it does keep allocating and discarding function literals, creating garbage on each call. A better solution would be one that avoided this memory churn. Having a sense for this isn't an idiom, but I think it counts for Go style, to be aware of your use of memory, and to find memory-efficient algorithms.

A purely stylistic issue is the name of the function fib_intern. Go style is to use camel-case as in fibIntern. But even this is redundant. Lower case always means non-exported, so simply 'fib' is enough. There's nothing wrong with having both Fib and fib. Go programmers understand that one is exported, one isn't, and that they are two different things. Perhaps you wanted a more descriptive name than just fib, but fib_intern isn't it. That tells your reader nothing that isn't obvious already.

Finally, the use of a relative import path, "./fib" is okay for a small exercise like this, but it's not a habit you want to form. Relative import paths have historically been problematic, and I think it's fine to do little experiments like this right on your GOPATH.

-
Thanks Sonia. You mention some good points. –  Anthony Cramp Mar 6 '13 at 11:01