Jviaches Blog: October 2015

3 WAYS TO IMPLEMENT FIBONACCI SERIES IN GOLANG

9:09 PM

Since we working with Go, it’s good time to play a bit with Fibonacci numbers. First of all it’s great in case of learning a new programming language and second, we will try to analyze a bit recurrent function and write it’s short iterative implementation. As a bonus we will write function that return function that return int .

But let’s starts from a theory. The definition of Fibonacci numbers state : Fn = Fn-1 + Fn-2 . The whole idea is find number by given its index.

Recursive implementation

func fibbRecc(numIndex int) (numValue int){
   if numIndex == 0 || numIndex == 1 {
      return numIndex
   }

   return fibbRecc(numIndex - 2) + fibbRecc(numIndex -1)
}

Note: Simple well known recursive approach. The first problem is possibility of stack overflow. The second one it’s exponential time of execution. Third problem is repetitive calculations. For example if we will calculate value at index 4 -> f(3) + f(2), it mean that f(2) will be calculated twice. And if we will calculate value at index 5 -> f(4) + f(3), it mean that f(3) will be calculated 3 times. And so on..

So suitable solution for third problem may be using some data structure (slice for instance) to store data and avoid unnecessary calculations.

2. Iterative function.

There are a short mathematical representation developed by Binet based ongolden ratio:

func fibShortIterative(numIndex float64) (float64){
   Phi := (1 + math.Sqrt(5)) / 2
   phi := (1 - math.Sqrt(5)) / 2

   return (math.Pow(Phi, numIndex) - math.Pow(phi, numIndex)) / math.Sqrt(5)
}

3. There is another way to write iterative Fibonacci function in Golang. Actually its a function that return function. And last one return int !

func fibIterFunc() func() int{
   x:=0
   y:=1

   return func() int{
      x,y = y,x+y
      return  x
   }
}

Usage:

f:=fibIterFunc()
for i := 0; i < 10; i++ {
   fmt.Print(f() )
}

Code (as always) can be found and downloaded from Github

3 ways to implement Fibonacci series in Golang

9:17 PM

But let’s starts from a theory. The definition of Fibonacci numbers state : Fn = Fn-1 + Fn-2 . The whole idea is find number by given its index.

Recursive implementation

func fibbRecc(numIndex int) (numValue int){
   if numIndex == 0 || numIndex == 1 {
      return numIndex
   }

   return fibbRecc(numIndex - 2) + fibbRecc(numIndex -1)
}

So suitable solution for third problem may be using some data structure (slice for instance) to store data and avoid unnecessary calculations.

2. Iterative function.

There are a short mathematical representation developed by Binet based ongolden ratio:

func fibShortIterative(numIndex float64) (float64){
   Phi := (1 + math.Sqrt(5)) / 2
   phi := (1 - math.Sqrt(5)) / 2

   return (math.Pow(Phi, numIndex) - math.Pow(phi, numIndex)) / math.Sqrt(5)
}

3. There is another way to write iterative Fibonacci function in Golang. Actually its a function that return function. And last one return int !

func fibIterFunc() func() int{
   x:=0
   y:=1

   return func() int{
      x,y = y,x+y
      return  x
   }
}

Usage:

f:=fibIterFunc()
for i := 0; i < 10; i++ {
   fmt.Print(f() )
}

Code (as always) can be found and downloaded from Github

Simple TODO list in Go [Tutorial]

9:13 PM

In this post i will introduce some basic (real basic) web development in go. We will start to implement TODO list and at the end of this topic it would’t be perfect but it will compile and show us proper results. May be in following topics we will continue to develop and expend this project. Sources will be available at the bottom of this post.

main.gtpl file (html based view) going to be like following:

< html>
< head>
    < title>all items< /title>
< /head>
< body>
< h1>List of todo items:< /h1>
    < div>
        < ul>
        {{ range $item := .}}
            < li>< input type="checkbox" id="{{ $item.Id }}" value="{{ $item.IsFinished }}" /> < label for="{{ $item.Id }}">{{ $item.Caption }} < /label>< /li>
        {{ end }}
        < /ul>

    < /div>
< /body>
< /html>

addItem.gtpl (another html based view) is looking as following:

< html>
< head>
    < title>Add new todo item< /title>
< /head>
< body>
< form action="/" method="POST">
    Caption: < input type="text" name="caption">
    < input type="submit" value="add">
< /form>
< /body>
< /html>

Controller will looks like following:

package main


import (
   "fmt"
   "log"
   "net/http"
   "html/template"
)


type ToDoItem struct  {
   Id int
   Caption string
   IsFinished bool
}

var TodoItemsSlice =  []ToDoItem{
}

func main() {
   fmt.Println("Initializing...")
   TodoItemsSlice = make([]ToDoItem,0)
   runServer()
}

func runServer(){
   fmt.Println("Starting sever...")

   // public views
   http.HandleFunc("/additem", addItemHandler )

   http.HandleFunc("/", handler)
   http.ListenAndServe(":8080", nil)
}

func handler(w http.ResponseWriter, r *http.Request) {
   captionFormValue := r.PostFormValue("caption")
   if  captionFormValue!= "" {

      fmt.Println("caption:", captionFormValue)

      newId := len(TodoItemsMap) + 1
      p := &ToDoItem{Id:newId, Caption: captionFormValue, IsFinished:false}
      TodoItemsSlice = append(TodoItemsSlice, *p)
   }

   t, err := template.ParseFiles("views/main.gtpl")
   if err != nil {
      log.Fatal("Can not parse views/main.gtpl "+ err.Error())
   }
   t.Execute(w, TodoItemsMap)
}


func addItemHandler(w http.ResponseWriter, r *http.Request) {
   log.Print("addItemHandler")
   t, _ := template.ParseFiles("views/additem.gtpl")
   t.Execute(w, t)
}

Firs of all lets start from Controller.

import (
   "fmt"
   "log"
   "net/http"
   "html/template"
)

Here we declare all packages we going to use. It right time to mention that code will not compile when you try to declare some package you are not going to use. By the way the same approach with defining unused variables.

Next we define ToDo item as struct (since i go there is no classes) and some TodoItemsSlice as slice. In short, slices are collections : it has an ability to add and remove items.

type ToDoItem struct  {
   Id int
   Caption string
   IsFinished bool
}

var TodoItemsSlice =  []ToDoItem{
}

Lets take a look in main andrunServer functions: In main function nothing special: printing to console regarding server initialization and creating new instance of empty slice. The running runServer function

It’s easy to see that server starting listening on port 8080 (browser port). In addition we can find two handlers: one for entering for the “localhost” and the second one when entering to “localhost:8080/additem” (in order to add more items in ToDo list).

func main() {
   fmt.Println("Initializing...")
   TodoItemsSlice = make([]ToDoItem,0)
   runServer()
}

func runServer(){
   fmt.Println("Starting sever...")

   // public views
   http.HandleFunc("/additem", addItemHandler )

   http.HandleFunc("/", handler)
   http.ListenAndServe(":8080", nil)
}

Now let’s skip default handler and talk about addHandler. In general handlers are functions that will executed when user will enter to specific URL. More about Go handlers you can find here.

Method addItemHandler gets two parameters: reponce and request. When use will enter to “localhost:8080/additem”, this handler will be executed. So first line is printing in console (by using log) and the we parse our view file by usage oftemplate. Usually view file can be represented as html but n this case it represented by gtpl which very similar to aspx file in APS.NET.

Interesting point here is that template.ParseFiles function returns two values (yes, it’s possible in go ) – result and error. Result represented by “t” variable, but we not going to use error at this point. If we define it (error variable) we have to use it, otherwise it will not compile. In order to avoid usage of returned variable we just using “_” telling Go that we are not interesting in it.

Another interesting point here is defining variables. In go there are two ways to define variable: by using “var” and by using “:=”. You can read about it here.

func addItemHandler(w http.ResponseWriter, r *http.Request) {
   log.Print("addItemHandler")
   t, _ := template.ParseFiles("views/additem.gtpl")
   t.Execute(w, t)
}

Let’s move on and take a look at our main handler.

func handler(w http.ResponseWriter, r *http.Request) {
   captionFormValue := r.PostFormValue("caption")
   if  captionFormValue!= "" {

      fmt.Println("caption:", captionFormValue)

      newId := len(TodoItemsMap) + 1
      p := &ToDoItem{Id:newId, Caption:captionFormValue, IsFinished:false}
      TodoItemsSlice = append(TodoItemsSlice, *p)
   }

   t, err := template.ParseFiles("views/main.gtpl")
   if err != nil {
      log.Fatal("Can not parse views/main.gtpl "+ err.Error())
   }
   t.Execute(w, TodoItemsMap)
}

At the beginning we trying to get caption value which we read from form. If found one, we create new todo item and populate it with proper data and append it to the slice. And the simply returning to the main.gtpl and showing results.

At this point i was encountered with this specific issue and it took me some time to get to the point and make it work. Since i spent some time on it, i suppose there are other who will encounter in the same issue. So let me show you how i resolved it.

Goal: output dynamically changed slice on the main.gtpl page.

Approach: within main handler we pass to the Execute function our slice which actually will be a context of main.gtpl. That’s it!

* Please let me know about any issue you encountered with (not compiling, not clear some point or untipattern, etc..)

Source code is available at GitHub.