CODEWITHSUNDEEP
f#
Alex Luk
Alex Luk

Reputation: 41

F# - Expected to be option but has a type

I was trying to build a binary tree in F# but when I tried to test my code, I met the problem above.

Here is my code:

type TreeNode<'a> = { Key: int; Val: 'a }
type Tree<'a> =  { LT: Tree<'a> option; TreeNode: TreeNode<'a>; RT: Tree<'a> option; }

//insert a node according to Binary Tree operation
let rec insert (node: TreeNode<'a>) (tree: Tree<'a> option) =
    match tree with
    | None -> {LT = None; RT = None; TreeNode = node }
    | Some t when node.Key < t.TreeNode.Key -> insert node t.LT
    | Some t when node.Key > t.TreeNode.Key -> insert node t.RT

let t = seq { for i in 1 .. 10 -> { Key = i; Val = i } }|> Seq.fold (fun a i -> insert i a) None

Upvotes: 0

Views: 208

Answers (2)

Alex Luk
Alex Luk

Reputation: 41

I worked it out now... It should be like below:

type TreeNode<'a> = { Key: int; Val: 'a }
type Tree<'a> =  { TreeNode: TreeNode<'a>; RT: Tree<'a> option; LT: Tree<'a> option; }

//insert a node according to Binary Tree operation
let rec insert (node: TreeNode<'a>) (tree: Tree<'a> option) =
    match tree with
    | None -> {LT = None; RT = None; TreeNode = node }
    | Some t when node.Key < t.TreeNode.Key -> {TreeNode = t.TreeNode; LT = Some(insert node t.LT); RT = t.RT}
    | Some t when node.Key > t.TreeNode.Key -> {TreeNode = t.TreeNode; RT = Some(insert node t.RT); LT = t.LT}

let t = seq { for i in 1 .. 10-> { Key = i; Val = i } }|> Seq.fold (fun a i -> Some(insert i a)) None

Upvotes: 0

Tomas Petricek
Tomas Petricek

Reputation: 243096

Your insert function takes option<Tree<'T>> but returns Tree<'T>. When performing the fold, you need to keep state of the same type - so if you want to use None to represent empty tree, the state needs to be optional type.

The way to fix this is to wrap the result of insert in Some:

let tree = 
  seq { for i in 1 .. 10 -> { Key = i; Val = i } }
  |> Seq.fold (fun a i -> Some(insert i a)) None

Upvotes: 1

Related Questions