Haskell: найдите значение в троичном дереве, и дерево не отсортировано

Question

На данный момент у меня есть тип данных дерева:

data TernaryTree a = EmptyTree
                   | Node a (TernaryTree a) (TernaryTree a) (TernaryTree a)
                   deriving (Show)

И я пытаюсь создать функцию, которая может зацикливать значение в троичном дереве. Дерево не отсортировано.

treeLook :: (Ord a)=> a -> TernaryTree a -> Bool
treeLook x EmptyTree = False
treeLook x (Node a left mid right) =
    if x /= a
        then do
        treeLook x left 
        treeLook x mid
        treeLook x right
        else 
        True

У меня есть это сейчас, но я не могу скомпилировать это. Это говорит:

Couldn't match expected type "m0 b0" with actual type "bool" on the line:
    treeLook x right

Answer 1

Do для монад.

Вместо этого используйте любой.

treeLook _ EmptyTree = False
treeLook x (Node y l m r) = any id [x == y, look l, look m, look r]
    where look = treeLook x

Как указано, или лучше использовать.

treeLook x (Node y l m r) = or [x == y, look l, look m, look r]
    where look = treeLook x

То, что мой фаворит был бы этим:

treeLook _ EmptyTree = False
treeLook x (Node y l m r) = x == y || any (treeLook x) [l, m, r]

Answer 2

do это ключевое слово, которое используется для включения некоторого синтаксического сахара для монад. В этом варианте монады не нужны.

Здесь есть два случая: EmptyTree это означает, что мы не смогли найти значение, поэтому мы возвращаем False,

Для Node мы можем проверить до четырех условий: это значение, которое мы ищем, значение в первом поддереве, значение во втором поддереве и значение в третьем поддереве. С момента, когда одна из проверок Trueмы можем вернуть True, Если все проверки не пройдены, мы вернемся Falseэто поведение логического или (||). Таким образом, мы можем написать это так:

treeLook :: Eq a => a -> TernaryTree a -> Bool
treeLook _ EmptyTree = False
treeLook x (Node a l m r) = x == a || treeLook x l || treeLook x m || treeLook x r

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

treeLook :: Eq a => a -> TernaryTree a -> Bool
treeLook x = go
    where go EmptyTree = False
          go (Node a l m r) = x == a || go l || go m || go r

Обратите внимание, что, поскольку дерево не отсортировано, нам не нужно Ord a ограничение типа, нам нужно только проверить равенство (здесь в x == a), Итак Eq a ограничение типа достаточно.

Answer 3

Одним из вариантов является использование elem, который проверяет, является ли значение элементом Foldable контейнер.

treeLook :: Eq a => a -> TernaryTree a -> Bool
treeLook = elem

Теперь вам просто нужно написать экземпляр Foldable, Одним из вариантов является включение DeriveFoldable расширение и просто использовать deriving (Show, Foldable) чтобы получить GHC, чтобы написать экземпляр для вас. Но ты многому не научишься таким образом. Итак, давайте рассмотрим несколько способов сделать это.

-- This import is needed for non-bleeding-edge GHC versions.
import Data.Monoid ((<>))

instance Foldable TernaryTree where
  -- Fold over the tree in pre-order
  foldMap _ EmptyTree = mempty
  foldMap f (Node x ls cs rs) =
    f x <> foldMap f ls <> foldMap f cs <> foldMap f rs

Но это повторилось foldMap сам по себе является своего рода "шаблоном", который вы можете извлечь, написав "катаморфизм" для деревьев:

cataTree :: r -> (a -> r -> r -> r -> r) -> TernaryTree a -> r
cataTree e _ EmptyTree = e
cataTree e f (Node x ls cs rs) =
  f x (cataTree e f ls) (cataTree e f cs) (cataTree e f rs)

Теперь вы можете определить foldMap таким образом:

foldMap f = cataTree mempty (\a lr cr rr -> f a <> lr <> cr <> rr)

Сейчас foldMap сама имеет более могущественную кузину, traverse, Так что другой вариант - начать там:

import Data.Traversable (fmapDefault, foldMapDefault)

instance Traversable TernaryTree where
  -- Traverse the tree in pre-order
  traverse f =
    cataTree (pure EmptyTree)
             (\a ls cs rs -> Node <$> f a <*> ls <*> cs <*> rs)

instance Functor TernaryTree where
  fmap = fmapDefault

instance Foldable TernaryTree where
  foldMap = foldMapDefault

Очевидно, что вы не в той точке, где вам захочется сделать что-то столь необычное, но такие методы действительно полезны, когда вы захотите быстро создать множество функций.