Применение функции к пользовательскому типу в F # - PullRequest
Новая
       13

Применение функции к пользовательскому типу в F #

2 голосов
/ 12 марта 2010

На пути к изучению F # я столкнулся с проблемой, которую не могу решить. Я определил пользовательский тип: 

type BinTree = 
  | Node of int * BinTree * BinTree
  | Empty

Я создал функцию, которая берет дерево, обходит его, добавляет посещаемые элементы в список и возвращает его: 

let rec inOrder tree = 
 seq{
 match tree with
  | Node (data, left, right) ->
   yield! inOrder left
   yield  data;
   yield! inOrder right
  | Empty -> ()
 }
 |> Seq.to_list;

Теперь я хочу создать функцию, подобную этой, которая берет дерево и функцию, пересекает ее и применяет функцию к каждому узлу, а затем возвращает дерево: 

mapInOrder : ('a -> 'b) -> 'a BinTree -> 'b BinTree

Это кажется легким, и, вероятно, так и есть! Но я не уверен, как вернуть дерево. Я пробовал это: 

let rec mapInOrder f tree = 
 match tree with
 | Node(data, left, right) ->
  mapInOrder f left
  Node(f(data), left, right)
  mapInOrder f right
 | Empty -> ()

но это возвращает единицу. Раньше я не работал с пользовательскими типами, так что я, вероятно, что-то там упустил!

Ответы [ 2 ]

8 голосов
/ 12 марта 2010

Попробуйте: 

let rec mapInOrder f = function
  | Node(a,l,r) ->
      let newL = mapInOrder f l
      let b = f a
      let newR = mapInOrder f r
      Node(b,newL,newR)
  | Empty -> Empty

Если функция не имеет побочных эффектов, порядок обхода не важен, и вместо этого вы можете написать: 

let rec map f = function
  | Node(a,l,r) -> Node(f a, map f l, map f r)
  | Empty -> Empty
2 голосов
/ 12 марта 2010

Совпадение - это выражение. Возвращает значение соответствующего случая. Это означает, что все случаи совпадения должны иметь одинаковый тип. Само выражение соответствия тогда имеет этот тип.

В первой попытке ваше предложение Empty вернулось () и, следовательно, имело тип юнитов, а не тот тип дерева, который вы искали.

Поскольку mapInOrder просто возвращает результат совпадения, он также принимает тип возвращаемого значения модуля.

Предложение Node было в порядке, поскольку его возвращаемое значение является результатом вызова mapInOrder, поэтому оно также приняло тип модуля и было выполнено требование, чтобы все предложения соответствия имели одинаковый тип.

Ключевое изменение в предложении kvb заключалось в том, чтобы предложение Empty возвращало дерево вместо единицы. Как только вы это сделаете, вы получите ошибки компилятора и предупреждения, указывающие на другие проблемы.

Вы можете часто справляться с такими проблемами, явно кодируя тип, который вам нужен, и затем просматривая, где отображаются ошибки и предупреждения компиляции.

...