Получить сумму и произведение целых чисел, определенных в дереве - PullRequest
Новая
       16

Получить сумму и произведение целых чисел, определенных в дереве

3 голосов
/ 06 ноября 2010

У меня есть небольшая проблема с пониманием того, как выполнить следующие действия в Haskell:

Допустим, у меня есть утверждение, подобное этому:

  • a * (b + c)
  • a + (b * c)
  • a + (b * (c + d))
  • a * (b + (c * d))
  • и т.д..и т. д.

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

data statement = Number Int 
               | Product statement statement 
               | Sum statement statement
               deriving (Eq, Show)

Для примера Tree toДля работы я использовал следующую функцию: 

a :: statement
a = Product (Number 2) (Sum (Number 5) (Number 1))

Теперь я хочу построить функцию treeResult, которая дает мне определенный результат моего оператора, но я не знаю, как решить эту проблему.Целое число, возвращаемое для вышеприведенного оператора, должно быть 12.

Моим первым предположением было написать функцию, которая принимает «оператор» в качестве параметра и возвращает int только для начинающих с простыми операторами. 

treeResult :: statement -> Int
treeResult (Number a) = a
treeResult (Product (Number a) (Number b)) = a*b
treeResult (Sum (Number a) (Number b)) = a+b

Теперь я знаю, что мне нужно что-то, что работает рекурсивно, но я не знаю, как написать это на haskell, может кто-нибудь помочь мне здесь, пожалуйста?

Ответы [ 2 ]

10 голосов
/ 06 ноября 2010

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

treeResult :: Statement -> Int
treeResult (Number x) = x

Очевидно, правильно до сих пор. Мы сопоставляем конструктор Number, извлекаем Int и возвращаем это - хорошо напечатано и делает то, что должно. 

treeResult (Product (Number a) (Number b)) = a*b
treeResult (Sum (Number a) (Number b)) = a+b

Это хорошо напечатано, но оно недостаточно общее. В этом шаблоне вы ограничиваете поля Product и Sum Number с, но на самом деле они могут быть любыми Statement. Так что вместо этого вам нужно определить Product / Sum: 

treeResult (Product a b) = ...
treeResult (Sum a b) = ...

Но мы не можем просто добавить / умножить два Statements. (+) и (*) не определены для них (мы вроде как делаем это прямо сейчас). Когда один операнд является Product, как мы можем получить его значение как Int? Оценивая это. Statement является рекурсивным, поэтому для его оценки нам нужна рекурсия. Таким образом, функция становится 

treeResult (Product a b) = (treeResult a) * (treeResult b)
treeResult (Sum a b) = (treeResult a) + (treeResult b)
4 голосов
/ 06 ноября 2010 
treeResult (Sum statement1 statement2) = treeResult statement1 + treeResult statement2

Аналогично для продукта. Это просто признание

  • результат (a + b) == результат a + результат b

(Кстати, тип данных должен называться Statement с заглавной буквы S. 

data Statement = Number Int | Product Statement Statement | Sum Statement Statement
                 deriving (Eq, Show)

)

...