۱۱ - ۱۷درخت باینری

حالا نظرمون رو به یه تایپ مشابهِ لیست جلب می‌کنیم. نوع‌ساز ِ درخت‌های باینری یه آرگومان می‌گیره، و مثلِ لیست بازگشتی ِه:

data BinaryTree a =
    Leaf
  | Node (BinaryTree a) a (BinaryTree a) 
  deriving (Eq, Ord, Show)

این درخت در هر گره یه مقدار از تایپِ ‏‎a‎‏ داره. هر گره ممکنه یه گره ِ انتهایی باشه، به اسمِ برگ، یا می‌تونه شاخه بده و دوتا زیردرخت داشته باشه. زیردرخت‌ها هم از تایپِ ‏‎BinaryTree a‎‏ هستن، پس این تایپ بازگشتی ِه. هر درخت باینری می‌تونه درخت باینری ِ دیگه‌ای رو در خودش ذخیره کنه، و همین به درخت‌ها عُمقِ دلخواه میده.

در بعضی موارد، درخت‌های باینری برای ساختاردهی و دسترسی به داده‌ها عملکردِ بهتری نسبت به لیست‌ها دارن، مخصوصاً اگه به نحوه‌ی ترتیب‌بندیِ مقادیر اشرافِ کامل داشته باشین، طوری که بدونین کِی برین "چپ" و کی برین "راست" تا به مقدارِ موردِ نظر برسین. از طرف دیگه، درختی که فقط از راست منشعب بشه، فرقی با لیست معمولی نداره. فعلاً خیلی با این چیزها کار نداریم، بعداً از استفاده و کاربرد صحیح از ساختارهای داده بیشتر صحبت می‌کنیم. بجاش چندتا تابع برای پردازش مقادیرِ ‏‎BinaryTree‎‏ می‌نویسین.

افزودن به داخلِ درختها

اولین چیزی که باید حواس‌مون بهش باشه، اینه که برای مرتب کردن مقادیر در درختها، ‏‎Ord‎‏ رو لازم داریم. اینطوری اگه چیزی کوچکتره، می‌تونیم بفرستیم‌ش یه جاهایی سمت چپ، یا اگه بزرگتر از گره ِ حاضر ِه، بِره یه جاهایی سمت راست. این "چپ کوچکتر، راست بزرگتر،" ترتیب رایجی برای درختهای باینری ِه – میشه برعکس هم باشه و فرقی نداره، ولی اینطوری کلاً آشناتر ِه، چون این ترتیب رو خیلی جاها دیدیم، مثلاً در محور اعداد. در هر صورت، هدف اینه که بدونیم کجا دنبالِ مقادیر بزرگتر یا کوچکتر از مقداری که روش هستیم بگردیم.

تابعِ ‏‎insert‎‏ یه مقدار رو داخلِ یه درخت وارد می‌کنه، یا اگه درختی هنوز وجود نداره، از طریقِ افزودن ِ مقادیر، راهی برای ساختِ یه درخت رو در اختیار میذاره. باز هم یادآوری می‌کنیم که مقادیر در هسکل تغییرناپذیر اند. مقدار رو به یه درختی که داریم اضافه نمی‌کنیم؛ هر بار که می‌خوایم یه مقدار به درختی اضافه بشه، یه درخت ِ جدید رو کامل می‌سازیم:

insert' :: Ord a
            => a
            -> BinaryTree a
            -> BinaryTree a
insert' b Leaf = Node Leaf b Leaf
insert' b (Node left a right)
  | b == a = Node left a right
  | b < a  = Node (insert' b left) a right
  | b > a  = Node left a (insert' b right)

فرمان پایه در ‏‎insert'‎‏ دو کار انجام میده. افزودن به یه درخت ِ خالی (‏‎Leaf‎‏) و شروع به ساختِ یه درخت ِ جدید، و همچنین حالتی که به انتهای درخت می‌رسیم رو به عهده می‌گیره. این سادگی اجازه میده تفاوت‌های جزئی بین این دو حالت رو نادیده بگیریم.

-- میشه "‎‏درخت خالی‏‎" ‎‏همون حالت‏‎ Leaf
Prelude> let t1 = insert' 0 Leaf
Prelude> t1
Node Leaf 0 Leaf

Prelude> let t2 = insert' 3 t1
Prelude> t2
Node Leaf 0 (Node Leaf 3 Leaf)

Prelude> let t3 = insert' 5 t2
Prelude> t3
Node Leaf 0
  (Node Leaf 3
    (Node Leaf 5 Leaf))

درخت‌های باینری و مشخصات‌شون رو بعداً در کتاب بررسی می‌کنیم. الان نمی‌خوایم روی مشخصات خودِ درخت‌های باینری تمرکز کنیم، بلکه با ساختارِ تایپ‌شون کار داریم. شاید تمرین‌های زیر به نظرتون سخت و خسته کننده بیان، اما به درک عمیق‌تر از طرز کار تایپ‌های بازگشتی کمک می‌کنن.

برای ‏‎BinaryTree‎‏ تابعِ ‏‎map‎‏ بنویسین

با توجه به تعریفِ ‏‎BinaryTree‎‏ در بالا، یه تابعِ نگاشت برای این ساختار داده بنویسین. واقعاً نیازی نیست چیزی از درخت‌های باینری بدونین تا این توابع رو بنویسین. همون ساختاری که در تعریف تایپ می‌بینین تنها چیزیه که لازم دارین. فقط باید توابعِ بازگشتی رو بنویسین.

هیچ الگوریتمِ خاصی نیاز نیست، ما هم انتظار نداریم درختها رو متعادل یا مرتب نگه دارین. یادتون هم باشه که ما هرگز یک بار هم چیزی رو تغییر ندادیم. فقط از داده ِ ورودی مقادیرِ جدید ساختیم. با توجه به این، تابعِ ‏‎mapTree‎‏ هم که تعریف می‌کنین، درخت ِ موجود رو تغییر نمیده – یه درخت ِ جدید بر مبنای اونی که هست می‌سازه (مثلِ نگاشت ِ توابع روی لیست‌ها).

دقت کنین که برای این تابع نیازی به ‏‎insert'‎‏ ندارین. ساختارِ درخت ِ ورودی رو حفظ کنین.

mapTree :: (a -> b)
        -> BinaryTree a
        -> BinaryTree b
mapTree _ Leaf = Leaf
mapTree f (Node left a right) =
  Node undefined undefined undefined

testTree' :: BinaryTree Integer 
testTree' =
  Node (Node Leaf 3 Leaf)
       1
       (Node Leaf 4 Leaf) 

mapExpected =
  Node (Node Leaf 4 Leaf)
       2
       (Node Leaf 5 Leaf)

-- mapTree تست تأیید برای
mapOkay =
  if mapTree (+1) testTree' == mapExpected
  then print "yup okay!"
  else error "test failed!"

این زیر چندتا راهنمایی برای نوشتنِ ‏‎mapTree‎‏ آوردیم.

اولین تطبیقِ الگو در تابعِ ‏‎mapTree‎‏ همون فرمان پایه هست (درخت ِ ورودی یه مقدارِ ‏‎Leaf‎‏ ِه). در این حالت نمیشه ‏‎f‎‏ رو اعمال کنیم چون ‏‎a‎‏ نداریم، پس کلاً نادیده گرفتیم‌ش. به این دلیل که تحت هر شرایطی باید یه مقدار با تایپِ ‏‎BinaryTree b‎‏ برگردونیم، ما هم یه مقدارِ ‏‎Leaf‎‏ برای خروجی نوشتیم.

در تطبیقِ الگو ِ دومِ تابعِ ‏‎mapTree‎‏، یه ‏‎Node‎‏ برمی‌گردونیم. دقت کنین که داده‌ساز ِ ‏‎Node‎‏ سه آرگومان می‌گیره:

Prelude> :t Node
Node :: BinaryTree a
     -> a
     -> BinaryTree a
     -> BinaryTree a

پس باید یه ‏‎BinaryTree‎‏، یه مقدارِ مجرد، و یه ‏‎BinaryTree‎‏ ِ دیگه بهش بدین. جملات زیر در اختیارتون هستن:

f :: (a -> b)

left :: BinaryTree a

a :: a

right :: BinaryTree a

mapTree :: (a -> b)
        -> BinaryTree a
        -> BinaryTree b

حالا ‏‎Node‎‏ ِ خروجی باید یه مقدار از تایپِ ‏‎b‎‏، و مقادیرِ ‏‎BinaryTree‎‏ با تایپِ ‏‎b‎‏ داخل‌شون داشته باشه. دو تابع در اختیارتون هست. یکی ‏‎(a -> b)‎‏ و یکی هم ‏‎BinaryTree‎‏های با تایپ ‏‎a‎‏ رو به ‏‎BinaryTree‎‏های با تایپِ ‏‎b‎‏ نگاشت میده. ببینیم چه می‌کنین.

چندتا پیشنهاد که ممکنه تو این تمرین کمک‌تون کنن:

درخت‌های باینری رو به لیست تبدیل کنین

تابع‌هایی که مقادیرِ ‏‎BinaryTree‎‏ رو به لیست تبدیل می‌کنن بنویسین. حتماً تابع‌تون رو با اون تست امتحان کنین.

preorder :: BinaryTree a -> [a]
preorder = undefined

inorder :: BinaryTree a -> [a]
inorder = undefined

postorder :: BinaryTree a -> [a]
postorder = undefined

testTree :: BinaryTree Integer 
testTree =
  Node (Node Leaf 1 Leaf)
       2
       (Node Leaf 3 Leaf)

testPreorder :: IO ()
testPreorder =
  if preorder testTree == [2, 1, 3]
  then putStrLn "Preorder fine!"
  else putStrLn "Bad news bears."

testInorder :: IO ()
testInorder =
  if preorder testTree == [1, 2, 3]
  then putStrLn "Ineorder fine!"
  else putStrLn "Bad news bears."

testPostorder :: IO ()
testPorstorder =
  if preorder testTree == [1, 3, 2]
  then putStrLn "Posteorder fine!"
  else putStrLn "Bad news bears."

main :: IO ()
main = do
  testPreorder
  testInorder
  testPostorder

برای ‏‎BinaryTree‎‏ تابعِ ‏‎foldr‎‏ بنویسین

با توجه به تعریفی که برای ‏‎BinaryTree‎‏ دادیم، یه کاتامورفیسم برای درخت‌های باینری بنویسین.

-- هر ترتیب پیمایشی‌ای قبوله
foldTree :: (a -> b -> b)
          -> b
          -> BinaryTree a
          -> b