Thực hiện một O (log n) Foldable.elem cho cây tìm kiếm nhị phân trong Haskell

Question

Hãy xem xét các định nghĩa sau đây cho cây nhị phân:

data Tree a = Nil | Node (Tree a) a (Tree a) 

Các dụ Foldable thể được định nghĩa như sau:

instance Foldable Tree where 
    foldr _ z Nil = z 
    foldr f z (Node l d r) = foldr f (f d (foldr f z l)) r 

Nhưng vấn đề là chức năng elem chạy trong O(n) thay vì O(log n). Khi tôi cố gắng thực hiện một phong tục elem:

elem x Nil = False 
elem x (Node l d r) 
    | x == d = True 
    | x < d = elem x l 
    | otherwise = elem x r 

tôi nhận được Could not deduce (Ord a) arising from a use of ‘<’. Làm cách nào để khắc phục sự cố này?

Answer 1

Bạn không thể sử dụng phương thức elem này cho lớp Có thể gập lại vì API có thể gập lại yêu cầu triển khai elem cho tất cả các trường hợp của nó. "An elem có tính đa hình cho tất cả Eq" là một sự lựa chọn có chủ ý trong thiết kế của kiểu chữ Foldable.

Chức năng elem của bạn, trong khi rất hữu ích, không tương thích với phương pháp elem cho kiểu chữ Foldable, vì nó không phải là đủ chung cho mong muốn của typeclass. Cách tốt nhất để xuất hàm elem cho loại của bạn là xác định một hàm riêng biệt bên ngoài typeclass.