Проверка того, сколько элементов дерева удовлетворяют предикату

Question

Я хочу подсчитать, сколько элементов в дереве «уважают» определенное правило.

Например:

Для типа данных:

data Tree = Leaf Int | Node Tree Int Tree 

и функции подписи:

nSatisfy :: (Int->Bool) -> Tree -> Int 

для ввода:

(>0) Tree 

она должна вернуть значения tre е, которые (> 0).

Вот что я пробовал:

nSatisfy :: (Int->Bool) -> Tree -> Int 
nSatisfy condition Leaf x = if condition x then 1 else 0 
nSatisfy condition (Node left x right) 
    |(if condition x then 1 else 0) + nSatisfy condition Tree 
    | otherwise = nSatisfy condition left || nSatisfy condition right 

Любая помощь?

UPDATE:

я нашел гораздо более простой способ сделать это:

nSatisfy :: (Int->Bool) -> Tree -> Int 
nSatisfy n (Leaf x) = if n x then 1 else 0 
nSatisfy n (Node left x right) = (if n x then 1 else 0) + (nSatisfy n left) + (nSatisfy n right) 

Answer 1

Эта функция делает слишком много за один раз: COUNT, проверить предикат и пройти сложный тип.

Я предлагаю написать функцию

listFromTree :: Tree -> [Int] 

и построить свой nSatisfy с listFromTree и функции Prelude length и filter.

---

Edit: OP нашел рабочий ответ сам, теперь вот мой код:

 
nSatisfy' p = length . filter p . listFromTree 

listFromTree :: Tree -> [Int] 
listFromTree (Leaf x) = [x] 
listFromTree (Node left x right) = listFromTree left ++ [x] ++ listFromTree right 

функции, которые проверяют что-то, то есть a -> Bool обычно называемый predicate и укороченный с p как в filter. n обычно является целым числом, а не функцией.

Answer 2

Ну, вот подсказка. Вы можете решить эту проблему гораздо легче, если вы разделить его на три части:

1. mapTree :: (Int -> Int) -> Tree -> Tree функция, которая применяет указанную функцию к каждому Int в дереве.
2. Функция, которая проверяет отдельное лицо Int и возвращает 1, если она удовлетворяет вашему состоянию, 0 в противном случае.
3. A sumTree :: Tree -> Int функция, которая суммирует все Int s в дереве.

Затем вы можете объединить эти три части, чтобы решить вашу проблему довольно легко. Более того, mapTree и sumTree будут полезны и для других проблем.

Answer 3

Нет ничего Неправильно с обновленной версией. Однако Луис Касильяс и Фрэнки побуждают вас думать о том, чтобы разбить идеи в вашем коде на наименьшие возможные части. Это, как правило, лучший способ справиться с проблемами программирования по нескольким причинам:

1. Человеческий мозг может думать только о так много сразу. Если вы разложите проблему на разные части или слои и будете думать только об этом, у вас будет гораздо больше шансов правильно ее решить.

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

3. Вы можете протестировать каждую часть решения отдельно. В этом случае проблема достаточно проста, чтобы протестировать все решение, но в наиболее реалистичных случаях, ожидая, пока вы не получите полное решение, прежде чем начать тестирование, вы проведете вниз по кроличьей норе: «Я знаю, что это неправильно, но я не знаю, t знать где ».

4. Как только вы нарушили свою проблему на мелкие кусочки, вы, скорее всего, обнаружите, что Другие люди уже решили эти проблемы. Когда-нибудь скоро ваше исследование Haskell приведет вас к структурам и функциям полиморфных данных. Обобщая ваш тип Tree, вы получите возможность использовать библиотечные функции, такие как toList, fmap и sum, создавая свое решение из частей решения, написанных для вас другими людьми.