유전자 정렬을위한 하스켈 바이너리 트리 술어

Question

하스켈을 처음 접했고이 사실을 알 수 없다. 주어진 이진 트리의 Node이 자식보다 큰지 확인하는 방법은 무엇입니까?

module IntTree where 

data IntTree = Leaf Int 
      | Node Int IntTree IntTree 
      deriving (Eq,Show) 

t1 :: IntTree 
t1 = Node 1999 (Node 1963 (Leaf 1925) 
          (Leaf 1933)) 
       (Node 1956 (Leaf 1932) 
          (Leaf 1924)) 


t2 :: IntTree 
t2 = Node 1999 (Node 1922 (Leaf 1925) 
          (Leaf 1933)) 
       (Node 1956 (Leaf 1932) 
          (Leaf 1924)) 

descendingTree :: Ord a => IntTree -> Bool 

는 노드의 값이 두 아이의 노드의 값보다 큰 트리의 모든 노드에 대한 사실 여부를 신호, IntTree을 얻을 것이다 대가로 나에게 부울을 줄 것이다 기능 descendingTree; 물론 아이들이 있다면. 이 함수를 작성하려면 어떻게해야합니까?

Answer 1

대답은 : 천천히 직접 데이터 유형 정의에 따라. 항상 두 아이가 , 경우

leaf _ = True 

가이 노드의; 경우

descendingTree :: IntTree -> Bool  -- no `a`, so no `Ord a` too 
-- data IntTree = Leaf Int 
descendingTree (Leaf i) = leaf i 
--    | Node Int IntTree IntTree 
descendingTree (Node i  lt  rt ) = node i lt rt 

그것은 확인 아무것도, 잎의 이것은 그 타입 정의에 의해 보증된다. 이 유형에는 다른 가능성이 없습니다. 여기

node i lt rt = 

당신은 테스트 작성해야 : 두 검사가 수행됩니다

 i > value lt && 
     i > value rt && 

을; 하나가 실패하면 &&식이 실패하고 False을 반환합니다. 좋은. 두 가지 테스트가 성공한다면 어떨까요?

 every_node_is_greater .... && 
     every_node_is_greater .... 

빈칸을 채울 수 있습니까?

every_node_is_greater에 대한 정의를 쓸 수 있습니까? 그럴 필요가 있니?

물론 두 기능 leaf 및 node은 완전히 중복됩니다. 그들은 우리를 위해 글쓰기 블록을 제거하기 위해 여기서 정신을 발판으로 삼았습니다. :) 보통 descendingTree 정의의 해당 절에서 코드를 작성합니다.

여기에 더 많은 정의가 필요합니다. value은 노드의 "가치"를 알 수있는 방법이 있다면 무엇이 문제 공간을 탐험하면서 도입 한 새로운 추상화입니까? ? 우리는 구체적인 내용을 나중에 다룰 것입니다 ... "). 이제 마침내 육체가 될 때입니다. 다시 말하면, 간단히 (그리고 천천히) 유형을 따르고 그것이 나타내는 경우를 처리하십시오.