开发者

how to make a tree from a given data with F#

can somebody teach me how to make a tree from a given data using F#? for example: a list of numbers or a list of city's name and etc . I don't have any clue how to make tree in F#, need help here :)

for example: the input开发者_运维技巧 is from run-time, assume it's from a text file: a list name of city

the output result: graph


Wikipedia has a list of common ways graph data is represented which should help you if you're trying to load graph data from a file. Once you have loaded the data search Stack Overflow. There are plenty of questions with tree implementations in them. Here are a few.

  • Help Needed Creating a Binary Tree Given Truth Table
  • Help in designing a tree structure - Tension between functional and OOP
  • Pretty print a tree
  • F#: Recursive collect and filter over N-ary Tree
  • What's wrong with my tree traversal code?


One possible solution would be to use Discriminated Unions to represent you data (in your case cities or numbers). The problem is, that you also need to know what relationship(s) between your cities you want to express.

e.g. you can express the relationship "alphabetical ordering" of your cities or "closest neighbored city" or "order by number of citizens". As you said your input is only a list of city names, I assume that you want the tree to order your cities by alphabet (i.e. expressing the "alphabetical ordering" relationship) in this case one solution could be:

let cities = ["Munich"; "Rome"; "Florence"; "Berlin"; "Paris"; "Marseille"]

type Tree<'A> =
| Node of Tree<'A> * 'A * Tree<'A>
| Leaf

let rec insert tree element = 
    match element, tree with
    | x, Leaf                    -> Node(Leaf, x, Leaf)
    | x, Node(l,y,r) when x <= y -> Node((insert l x), y, r)
    | x, Node(l,y,r) when x >  y -> Node(l, y, (insert r x))

let rec flatten = function
| Leaf        -> []
| Node(l,x,r) -> flatten l @ [x] @ flatten r

let sort xs = xs |> List.fold insert Leaf
                 |> flatten


let cityTree     = List.fold insert Leaf cities
let sortedCities = sort cities
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜