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
精彩评论