Implementing a Stack in F#. Tail Recursion.

0

Viral F#

Since Push requires stacks to manipulate its data, we need an implementation of this data structure. There is of course a .NET implementation, however, it is not a “functional” data structure, in a sense that it is mutable. It is easy enough to implement our own, purely functional, immutable stack.

F# list is a logical choice for an underlying implementation. It derives from Seq (i.e. implements all IEnumerable flavors), has a useful length property which we would like to have for our stack as well:

What remains is to implement basic operations, which are all static members of the Stack module.

These are pretty straightforward. pop function has a slight quirk: we would like to return both the value of the head of the stack as well as “the rest” of the stack. So the return type in this case is a tuple.

Another slight irregularity: stack functions work on…

View original post 270 more words

Advertisements

Bullet points formatter

0

Hey guys,

So this week I worked on a small code kata. The purpose of this project is to simply be able to format text into a bullet point like any text editor allows you to do it. To complete this challenge, I decide to use F# since it’s so great for prototyping and get fast results. The project had the following requirements:

  • Produce an outline of headings
  • Heading values are provided

Here’s an example of what should be printed in console :

  1. Software development is

A. An awesome thing to do

2.  Why do code katas ?

A. They are

i. Entertaining

ii. Challenging

So as we can, we have three different level of formatting to do on the string and heading values are provided for the formatting. Those requirements led to the following code :

code language="fsharp"]
 open System
 open System.Linq 

type Indexes = {
     Primaryint 
     Secondary int
     Third int 
 }
type BulletPointStyle =
     | NumberedStyle 
     | LetteredStyle 

type HeadingWeight = 
     | HW1 
     | HW2 
     | HW3 

type Heading = {
     Weight HeadingWeight
     Text string
 }

type Node = {
     Line Heading 
 }

type Outline = {
     Text string 
     HeadingIndexes Indexes
 }
 with 
     member x.addContent str = { x with Text = x.Text + Environment.NewLine  + str }

let updateIndexes (oOutline) (hHeading) = 
     match h.Weight with 
     | HW1 -> 
         let indexes = { o.HeadingIndexes with Primary = o.HeadingIndexes.Primary + 1Secondary = 1 ;Third = 1 }
         { o with HeadingIndexes = indexes }
     | HW2 -> 
         let indexes = { o.HeadingIndexes with Secondary = o.HeadingIndexes.Secondary + 1Third = 1 }
         { o with HeadingIndexes = indexes }
     | HW3 ->
         let indexes = { o.HeadingIndexes with Third = o.HeadingIndexes.Third + 1 }
         { o with HeadingIndexes = indexes }       

let determineBulletStyle (hwHeadingWeight) = 
     match hw with 
     | HW1 -> NumberedStyle
     | HW2 | HW3 -> LetteredStyle

let getLetter (indexint)=
     (("ABCDEFGHIJKLMNOPQRSTUVWXYZ".[index-1]).ToString())

let formatTextNode(nNode) (oOutline)
     let header = n.Line
     let mutable text = ""
     let style = determineBulletStyle header.Weight
     let indexer = o.HeadingIndexes
     match style with 
     | NumberedStyle -> 
         text <(indexer.Primary.ToString()) + "" + header.Text
     | LetteredStyle -> 
         let head = 
             match header.Weight with 
             | HW2 -> String.Join(""Enumerable.Repeat(" ",4)) + getLetter indexer.Secondary
             | HW3 -> String.Join(""Enumerable.Repeat(" "8)) + String.Join(""Enumerable.Repeat("i"indexer.Third))
             | _ -> ""
          text <head + "" + header.Text 
     text

// Folds an Outline and a list Nodes to an Outline
 let formatTextOutline(nodeListNode list) =
     ( { Text = ""HeadingIndexes = { Primary = 1Secondary = 1Third = 1 } }nodeList) 
     ||> Seq.fold (fun outline node -> 
         let text = formatTextNode node outline
         let outline = outline.addContent text
         updateIndexes outline node.Line
     )

[<EntryPoint>]
 let main argv = 
     let nList = 
         [
              { Line = { Weight = HW1Text = "Software development is" } } 
              { Line ={ Weight = HW2Text = "Super fun" } } 
              { Line ={ Weight = HW3Text = "But challenging" } } 
              { Line ={ Weight = HW3Text = "And rewarding" } }
         ]
     let outline = formatTextOutline nList
     printf "%s" outline.Text
     0 // return an integer exit code

[/code]

So basically, the process is made thanks to formatTextOutline and formatTextNode. Through those functions, I can create the Outline record that holds the formatted text and the indices for the level of formatting (Indexes). When I get in formatTextNode, I can first establish the heading style of the line thanks BulletPointStyle discriminated union(DU) type. Using the style enables me to know if I only have to take care of numbers or the letters. When I have to deal with characters, the HeadingWeight DU becomes handy to see whether or not I’ll be using a single tab (4 spaces) or a 2 tabs (8 spaces).

There you go ! 🙂

Kevin out

Why F#?

0

Didactic Code

If you’ve been following along with my posts over the past six months or so you can probably imagine that I’ve been asked some variation of this post’s title more than a few times. One question that I keep getting is why I chose F# over some other functional languages like Haskell, Erlang, or Scala. The problem with that question though is that it’s predicated on the assumption that I actually set out to learn a functional language. The truth is that moving to F# was more of a long but natural progression from C# rather than a conscious decision.

The story begins about two and a half years ago. I had pretty much burned out and was deep into what I can only begin to describe as a stagnation coma. I stopped attending user group meetings; I cut way back on reading; I pretty much stopped…

View original post 2,559 more words

Posted in F#

Book Review: F# for C# Developers

0

This book looks interesting enough to give it a try. I’ll order a copy today.

The Education of a Programmer (Me)

I recently read F# for C# Developers by Tao Liu. As usual, the disclaimer is that I received a copy of the book for free in return for the review. This one was a challenge. Not because of the programming paradigm shift from imperative driven programming in C# to functional programming in F#, but because the density of the book and my having read a different book on F# rather recently.

Mr Liu is most certainly an expert on F#, both from his work at Microsoft and this book. However there were times when I felt a little frustrated in reading the book. My favourite chapter of this book was Chapter 3 where he examines design patterns which can be found in C# and then applies these patterns to F# code. It remains dense reading, but it demonstrates those patterns very well. Mr Liu takes the notion, as I read…

View original post 295 more words

Posted in F#