Chương 14: Khóa kéo

Trở về Mục lục cuốn sách

Dù cho tính thuần khiết của lập trình hàm trong Haskell đem lại nhiều lợi ích, nó cũng khiến chúng ta phải giải quyết một số bài toán theo cách khác so với khi làm bằng ngôn ngữ không thuần khiết. Vì tính minh bạch về tham chiếu, một giá trị cũng tốt ngang bằng giá trị khác trong Haskell nếu chúng cùng biểu diễn một thứ.

Vì vậy nếu ta có một cây dữ liệu gồm toàn những số năm và ta muốn thay một con số trong đó thành sáu, thì ta phải bằng cách nào đó biết được chính xác số năm nào trên cây được thay đổi. Ta phải biết vị trí của nó trên cây. Trong ngôn ngữ không thuần túy, ta chỉ cần ghi lại vị trí lưu trữ của số năm đó trong bộ nhớ rồi thay đổi nó. Nhưng trong Haskell, số năm nào cũng tốt như nhau, vì vậy ta không thể phân biệt chúng dựa vào vị trí lưu trong bộ nhớ. Và ta cũng không thể thay đổi thứ gì; khi ta nói thay đổi một cây dữ liệu thì thực ra là ta lấy cây đó rồi trả lại một cây mới gần giống với cây ban đầu, chỉ hơi khác đi.

Một điều ta có thể làm là ghi nhớ đường đi từ điểm gốc của cây đến phần tử mà ta muốn thay đổi. Ta có thể nói rằng, đem lấy cây này, đi sang trái, đi sang phải rồi lại sang trái và thay đổi phần tử tại ví trí đó. Dù cách này hoạt động được, có thể nó sẽ kém hiệu quả. Nếu sau này ta muốn thay đổi một phần tử ở gần với phần tử trước đây đã thay đổi, ta vẫn phải đi lại từ gốc cây đến phần tử đang xét!

Trong chương này, ta sẽ xem bằng cách nào có thể nhận lấy một cấu trúc dữ liệu rồi tập trung vào một phần của nó theo cách sao cho việc thay đổi các phần tử trở nên dễ dàng và di chuyển trong cấu trúc này được hiệu quả. Thật hay!

Bước đi dạo

Cũng như khi ta học môn sinh vật, có nhiều loại cây khác nhau, vì vậy hãy lựa lấy một hạt giống để ta trồng nên cây của mình. Đây này:

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

Như vậy ta có một cây hoặc là rỗng, hoặc là một điểm nút gồm một phần tử và hai cây con. Sau đây là ví dụ của một cây như vậy, mà tôi cho bạn miễn phí!

freeTree :: Tree Char
freeTree = 
    Node 'P'
        (Node 'O'
            (Node 'L'
                (Node 'N' Empty Empty)
                (Node 'T' Empty Empty)
            )
            (Node 'Y'
                (Node 'S' Empty Empty)
                (Node 'A' Empty Empty)
            )
        )
        (Node 'L'
            (Node 'W'
                (Node 'C' Empty Empty)
                (Node 'R' Empty Empty)
            )
            (Node 'A'
                (Node 'A' Empty Empty)
                (Node 'C' Empty Empty)
            )
        )

Và sau đây là hình biểu diễn cái cây này:

polly says her back hurts

Bạn để ý thấy W trên cây chứ? Chẳng hạn, ta muốn đổi nó thành P. Ta sẽ làm việc này thế nào? Ồ, một cách làm là khớp mẫu lên cây đến khi ta thấy được phần tử được định vị theo cách trước hết là đi sang phải, rồi sang trái, sau đó là thay đổi phần tử được xét. Sau đây là mã lệnh thực hiện điều này:

changeToP :: Tree Char -> Tree Char
changeToP (Node x l (Node y (Node _ m n) r)) = Node x l (Node y (Node 'P' m n) r)

Ặc! Viết thế này không những xấu xí mà còn khó hiểu. Có gì xảy ra ở đây vậy? À, ta khớp mẫu lên cây và đặt tên cho phần tử gốc là x (mà sẽ trở thành 'P' ở điểm gốc) và cây con bên trái là l. Thay vì đặt tên cho cây con bên phải, ta lại tiếp tục khớp mẫu lên nó. Ta tiếp tục việc khớp mẫu này đến khi đạt tới cây con mà gốc là 'W'. Một khi làm được việc này, ta dựng lại cây, và chỉ có cây con chứa 'W' ở gốc bây giờ mới có phần tử 'P'.

Có cách nào tốt hơn để thực hiện việc này không? Liệu việc lập riêng một hàm nhận vào một cây cùng với danh sách các hướng đi thì sao? Các hướng đi sẽ là L hoặc R, tương ứng với trái và phải, đồng thời ta sẽ thay đổi phần tử mà ta có được sau khi lần theo các hướng đã cho. Sau đây là mã lệnh:

data Direction = L | R deriving (Show)
type Directions = [Direction]

changeToP :: Directions-> Tree Char -> Tree Char
changeToP (L:ds) (Node x l r) = Node x (changeToP ds l) r
changeToP (R:ds) (Node x l r) = Node x l (changeToP ds r)
changeToP [] (Node _ l r) = Node 'P' l r

Nếu phần tử dầu thuộc danh sách các hướng đi là L, ta sẽ tạo ra một cây mới gần giống cây cũ, chỉ khác là cây con bên trái có một phần tử được đổi thành 'P'. Khi ta gọi đệ quy changeToP, ta chỉ cho nóa phần đuôi của danh sách các hướng đi, vì ta đã đi về phía trái rồi. Ta cũng làm điều tương tự trong trường hợp với R. Nếu danh sách các hướng đi là rỗng, có nghĩa rằng ta đã đến đich, thì cần trả lại một cây gần giống cây ban đầu, chỉ khác ở phần tử gốc bây giờ là 'P'.

Để tránh việc phải in lại cả cây, ta hãy lập một hàm nhận vào một danh sách các hướng đi rồi cho ta biết phần tử tại điểm đến là gì:

elemAt :: Directions -> Tree a -> a
elemAt (L:ds) (Node _ l _) = elemAt ds l
elemAt (R:ds) (Node _ _ r) = elemAt ds r
elemAt [] (Node x _ _) = x

Thực ra hàm này gần giống với changeToP, chỉ khác ở chỗ thay vì ghi nhớ thông tin trên đường đi rồi dựng lại cây, thì nó phớt lờ mọi thứ chỉ trừ điểm đến. Ở đây ta đã thay 'W' bằng 'P' rồi xem liệu sự thay đổi của cây mới có biểu hiện không:

ghci> let newTree = changeToP [R,L] freeTree
ghci> elemAt [R,L] newTree
'P'

Hay đấy, dường như có hoạt động rồi. Trong những hàm này, danh sách các hàm đóng vai trò của mục tiêu, vì nó tập trung vào đúng một cây con từ cây ban đầu của ta. Một danh sách hướng đi, chẳng hạn như [R] tập trung vào cây con bên phải của gốc. Một danh sách rỗng tập trung vào chính cây đó.

Mặc dù phương pháp này có vẻ hay, nhưng có thể nó sẽ kém hiệu quả, đặc biệt là nếu ta muốn liên tục thay đổi các phần tử. Giả sử ta có một cây rất lớn và một danh sách hướng đi dài để chỉ đến một phần tử ở đáy dưới cùng thuộc cây. Ta dựa vào danh sách hướng đi để di chuyển trên cây và thay đổi một phần tử ở dưới đáy. Nếu ta muốn thay đổi một phần tử khác gần sát phần tử mà ta vừa thay đổi, ta phải khởi đầu lại từ điểm gốc cây rồi đi đến đáy của cây lần nữa! Thật nhiêu khê!

Ở mục tiếp theo, ta sẽ tìm một cách tốt hơn để tập trung vào cây con, cách làm này cho phép ta chuyển sự tập trung đến các cây con gần đó một cách hiệu quả.

Vệt dài những mẩu vụn bánh mì

whoop dee doo

Được rồi, như vậy bằng việc tập trung vào một cây con, ta muốn có điều tốt hơn là chỉ một danh sách các hướng đi cần phải theo từ điểm gốc của cây. Chẳng phải sẽ có ích hơn nếu ta xuất phát từ điểm gốc cây rồi di chuyển sang trái hoặc phải từng bước một rồi rải vụn bánh mì để làm dấu ư? Nghĩa là, khi đi sang trái, ta ghi nhớ rằng qua trái, và khi sang phải cũng ghi nhớ là qua phải. Hẳn là được, ta có thể thử xem.

Để biểu thị các mẩu vụn bánh mì, ta cũng sẽ dùng một danh sách các Direction (vốn là L hoặc R), chỉ khác là thay vì gọi nó là Directions, ta sẽ gọi nó là Breadcrumbs, vì các hướng đi này sẽ bị đảo ngược bởi ta đang rải nó trong quá trình đi xuống cây dữ liệu:

type Breadcrumbs = [Direction]

Sau đây là một hàm nhận vào một cây và một số mẩu vụn bánh mì rồi đi sang cây con bên trái đồng thời thêm L và đầu danh sách biểu diễn những mẩu vụn bánh:

goLeft :: (Tree a, Breadcrumbs) -> (Tree a, Breadcrumbs)
goLeft (Node _ l _, bs) = (l, L:bs)

Ta phớt lờ phần tử tại gốc cây và cây con bên phải rồi chỉ trả lại cây con bên trái cùng với những mẩu vụn bánh trước đây với L đứng ở đầu. Còn sau đây là hàm để đi sang phải:

goRight :: (Tree a, Breadcrumbs) -> (Tree a, Breadcrumbs)
goRight (Node _ _ r, bs) = (r, R:bs)

Nó cũng hoạt động theo cách tương tự. Ta hãy dùng các hàm này để lấy cây freeTree của ta rồi đi sang phải, tiếp theo là sang trái:

ghci> goLeft (goRight (freeTree, []))
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])

almostthere

Được rồi, bây giờ ta có một cây chứa 'W' ở gốc cây và 'C' ở gốc thuộc cây con bên trái và 'R' ở gốc thuộc cây con bên phải. Các mẩu vụn bánh là [L,R], vì đầu tiên ta đi sang bên phải, sau đó sang trái.

Để cho việc di chuyển trên cây được rõ ràng hơn, ta có thể dùng hàm -: vốn được định nghĩa như sau:

x -: f = f x

Hàm này cho phép ta áp dụng hàm lên giá trị bằng cách trước hết là viết ra giá trị, sau đó viết dấu -: rồi đến hàm. Theo đó, thay vì goRight (freeTree, []), ta có thể viết (freeTree, []) -: goRight. Bằng cách này, ta có thể viết lại đoạn mã lệnh trên để cho thấy rõ hơn là trước hết ta đi sang phải rồi sang trái:

ghci> (freeTree, []) -: goRight -: goLeft
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])

Đi ngược lại

Vậy sẽ ra sao nếu bây giờ ta muốn đi ngược lại theo cây? Căn cứ vào những vụn bánh, ta biết rằng cây hiện tại là cây con bên trái của cây mẹ, và bản thân cây này là cây con phải của cây mẹ cấp cao hơn, nhưng tất cả chỉ có vậy. Thông tin này chưa đủ cho ta biết về mẹ của cây con hiện thời để ta có thể leo ngược lại. Trong trường hợp này, đó là phần tử ở cây mẹ cùng với cây con bên phải của nó.

Nhìn chung, một mẩu vụn bánh cần chứa tất cả dữ liệu cần thiết để dựng lại điểm nút của cây mẹ. Như vậy nó cần phải có thông tin từ tất cả những đường đi mà ta đã không chọn, đồng thời cũng phải biết được hướng đi mà ta chọn, nhưng không được phép chứa cây con mà ta hiện đang tập trung xem xét. Đó là vì ta đã có cây con này là thành phần thứ nhất của bộ, nên nếu cũng có nó trong số các mẩu vụn bánh, thì thành thử sẽ dư thừa thông tin.

Ta hãy sửa lại mã lệnh viết cho vụn bánh để chúng cũng chứa thông tin mà trước đây ta đã phớt lờ trong quá trình đi sang trái và phải. Thay vì Direction, ta sẽ lập một kiểu dữ liệu mới:

data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) deriving (Show)

Bây giờ, thay vì chỉ có L, ta có một LeftCrumb trong đó cũng chứa phần tử thuộc điểm nút mà ta bắt đầu di chuyển và cây bên phải mà ta không đi vào. Thay vì R, ta có RightCrumb, trong đó chứa phần tử của nút mà ta bắt đầu di chuyển và cây con trái mà ta không đi vào.

Bây giờ những mẩu bánh đã chứa tất cả những thông tin cần thiết để dựng lại cây mà ta đã đi dọc theo. Như vậy thay vì chỉ là những vụn bánh thông thường, bây giờ chúng đã giống như những đĩa mềm mà ta bỏ lại dọc đường, vì chúng có chứa nhiều thông tin hơn là đơn thuần hướng đi mà ta đã chọn.

Tóm lại, mỗi mẩu vụn bánh bây giờ như một nút trên cây, nhưng ở đó trống không. Khi ta di chuyển sâu hơn vào trong cây, thì vụn bánh sẽ mang theo tất cả những thông tin từ nút ta vừa rời khỏi, chỉ trừ cây con mà ta chọn để tập trung vào. Cũng cần lưu ý khoảng trống ở đâu. Trong trường hợp LeftCrumb, ta biết rằng khi di chuyển về bên trái, và cây con bị khuyết thiếu là cây bên trái.

Ta hãy đồng thời thay đổi kiểu tương đồng Breadcrumbs để phản ánh điều này:

type Breadcrumbs a = [Crumb a]

Tiếp theo, ta phải sửa đổi các hàm goLeftgoRight để lưu trữ thông tin về các đường đi mà ta không lựa chọn trong số các mẩu vụn bánh, thay vì việc phớt lờ thông tin này như đã làm trước đây. Bên dưới là hàm goLeft:

goLeft :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goLeft (Node x l r, bs) = (l, LeftCrumb x r:bs)

Bạn có thể thấy rằng nó khá giống với hàm goLeft trước đây, chỉ khác ở chỗ thay vì thêm mỗi L vào đầu danh sách chứa các vụn bánh, ta lại thêm một LeftCrumb để nhấn mạnh rằng ta đi về phía trái đồng thời cung cấp cho LeftCrumb phần tử thuộc điểm nút mà ta vừa rời khỏi (đó là x) và cây con bên phải mà ta quyết định không đi vào.

Lưu ý rằng hàm này đã giả sử rằng cây đang xét không phải Empty. Một cây rỗng thì không có cây con nào, vì vậy nếu ta thử đi về phía trái của một cây rỗng thì sẽ xuất hiện lỗi, vì phép khớp mẫu đối với Node sẽ không thành công và không có dạng mẫu nào đảm nhiệm được Empty.

goRight cũng tương tự:

goRight :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goRight (Node x l r, bs) = (r, RightCrumb x l:bs)

Đến đây ta đã có thể đi sang trái và phải. Điều cần làm bây giờ là khả năng đi ngược lại dựa trên việc ghi nhớ những thông tin về nút của cây mẹ và những đường đi mà ta không vào. Sau đây là hàm goUp:

goUp :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goUp (t, LeftCrumb x r:bs) = (Node x t r, bs)
goUp (t, RightCrumb x l:bs) = (Node x l t, bs)

asstronaut

Ta tập trung vào cây t rồi kiểm tra xem cái Crumb mới nhất là gì. Nếu là LeftCrumb, thì ta đi lập nên một cây mới trong đó cây hiện tại t của ta là cây con bên trái, đồng thời dùng thông tin về cây con bên phải mà ta đã không đi vào để điền nốt phần còn lại của Node. Hãy hình dung xem, vì ta đã di chuyển ngược lại và nhặt mẩu vụn bánh gần nhất để tái tạo lại cây mẹ, nên danh sách mới chứa các vụn bánh sẽ không bao gồm mẩu vụn này.

Lưu ý rằng hàm này gây ra một lỗi nếu ta đã ở ngọn cây mà vẫn muốn di chuyển lên. Sau này, ta sẽ dùng monad Maybe để biểu diễn khả năng thất bại khi di chuyển mục tiêu.

Với một cặp Tree aBreadcrumbs a, ta đã có tất cả thông tin để dựng lại toàn bộ cây, đồng thời ta cũng có mục tiêu nhắm vào một cây con. Phương pháp này cũng giúp cho phép ta dễ dàng di chuyển lên, sang trái và phải. Một cặp như vậy, chứa phần mục tiêu của cáu trúc dữ liệu cùng môi trường quanh nó, thì được gọi là “khóa kéo”, vì việc di chuyển mục tiêu lên hoặc xuống dọc theo cấu trúc dữ liệu cũng giống như hoạt động của khóa kéo (phéc-mơ-tuya). Vì vậy việc tạo ra một kiểu tương đồng như sau sẽ rất hay:

type Zipper a = (Tree a, Breadcrumbs a)

Tôi muốn đặt tên kiểu tương đồng là Focus vì nó sẽ rõ nghĩa là ta đang tập trung vào một phần của cấu trúc dữ liệu, nhưng thuật ngữ khóa kéo (zipper) được dùng rộng rãi hơn để mô tả một cơ chế như vậy, nên ta sẽ thống nhất với tên gọi Zipper.

Thao tác với cây mục tiêu

Bây giờ khi ta có thể di chuyển lên và xuống, hãy lập nên một hàm để thay đổi phần tử ở gốc của cây con mà khóa kéo đang tập trung tới:

modify :: (a -> a) -> Zipper a -> Zipper a
modify f (Node x l r, bs) = (Node (f x) l r, bs)
modify f (Empty, bs) = (Empty, bs)

Nếu đang tập trung vào một điểm nút, ta có thể thay đổi phần tử tại gốc bằng hàm f. Nếu đang tập trung vào một cây rỗng, ta chỉ việc giữ nguyên nó. Bây giờ, ta có thể bắt đầu với một cây, di chuyển đi đâu tùy thích và thay đổi một phần tử, đồng thời vẫn giữ mục tiêu đến phần tử đó để ta có thể dễ dàng di chuyển lên, xuống. Một ví dụ:

ghci> let newFocus = modify (\_ -> 'P') (goRight (goLeft (freeTree,[])))

Ta đi sang trái, sang phải rồi thay đổi phần tử gốc bằng cách thay thế nó bằng 'P'. Mã lệnh thậm chí sẽ dễ đọc hơn nếu ta dùng -::

ghci> let newFocus = (freeTree,[]) -: goLeft -: goRight -: modify (\_ -> 'P')

Sau đó ta có thể di chuyển lên nếu muốn, và thay thế một phần tử với chữ 'X' bí hiểm:

ghci> let newFocus2 = modify (\_ -> 'X') (goUp newFocus)

Hoặc nếu ta viết nó bằng -::

ghci> let newFocus2 = newFocus -: goUp -: modify (\_ -> 'X')

Việc di chuyển lên thật dễ vì các mẩu vụn mà ta để lại đã hình thành nên một phần của cấu trúc dữ liệu mà ta không hướng mục tiêu đến, tuy vậy đường đi cần được đảo ngược lại, như ta lộn lại đôi tất. Đó là lý do mà khi muốn di chuyển lên, ta không phải xuất phát từ gốc và đi xuống, mà chỉ việc lấy ngọn của cây sau khi đã đảo ngược, bằng cách đó mà lật ngược trở lại một phần của cây rồi bổ sung nó vào cây mục tiêu hiện có.

Mỗi điểm nút có hai cây con, ngay cả khi những cây con này là cây rỗng. Vì vậy nếu ta đang hướng mục tiêu vào một cây rỗng, thì điều duy nhất ta có thể làm là thay thế nó bằng một cây con không rỗng, bằng cách này gắn cây vào một điểm nút lá. Mã lệnh để thực hiện điều này rất đơn giản:

attach :: Tree a -> Zipper a -> Zipper a
attach t (_, bs) = (t, bs)

Ta lấy một cây và một khóa kéo rồi trả lại một khóa kéo mới mà mục tiêu được thay thế bằng cây được cung cấp vào. Không những ta có thể mở rộng các cây theo cách này qua việc thay thế cây con rỗng bằng cây mới, mà đồng thời ta còn có thể thay thế toàn bộ cây con hiện có. Ta hãy gắn một cây vào phía ngoài cùng bên trái của cây freeTree hiện có:

ghci> let farLeft = (freeTree,[]) -: goLeft -: goLeft -: goLeft -: goLeft
ghci> let newFocus = farLeft -: attach (Node 'Z' Empty Empty)

Bây giờ, newFocus được hướng mục tiêu đến cây mà ta vừa gắn vào còn phần còn lại của cây này tồn tại dưới dạng đảo ngược trong các mẩu vụn. Nếu ta dùng goUp để đi hết lên ngọn cây, thì cũng được cây giống như freeTree song với một chữ 'Z' thêm vào vị trí ngoài cùng bên trái.

Tôi lên thẳng ngọn cây đây, trên này không khí trong lành quá!

Việc tạo ra một hàm để đi tuốt lên ngọn cây, bất kể là chúng ta có mục tiêu là gì, thật dễ dàng. Sau đây là hàm này:

topMost :: Zipper a -> Zipper a
topMost (t,[]) = (t,[])
topMost z = topMost (goUp z)

Nếu vệt những mẩu bánh mì là danh sách rỗng, điều đó có nghĩa là ta đã ở gốc cây rồi, vì vậy chỉ việc trả lại mục tiêu hiện có. Nếu không, ta phải đi lên để lấy mục tiêu là nút trên cây mẹ rồi áp dụng hàm topMost đối với nút này theo cách đệ quy. Như vậy bây giờ ta đã có thể đi khắp cây rồi, qua bên trái hoặc phải, đi lên, áp dụng hàm modifyattach trong quá trình di chuyển và khi thực hiện sửa đổi xong, thì dùng topMost để tập trung vào điểm gốc cây để xem những thay đổi mà ta vừa thực hiện, nhưng dưới góc nhìn thích hợp.

Mục tiêu hướng về danh sách

Khóa kéo có thể được dùng với nhiều cấu trúc dữ liệu, vì vậy sẽ không ngạc nhiên khi thấy nó có thể dùng để hướng mục tiêu về các danh sách con của một danh sách. Sau hết, danh sách rất giống với cây, chỉ có điều một điểm nút trên cây thường có một (hoặc không có) phần tử và nhiều cây con, trong khi đó một điểm nút trong danh sách chỉ có một danh sách con. Khi tự lập riêng các danh sách, ta đã định nghĩa kiểu dữ liệu riêng như sau:

data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)

the best damn thing

So sánh điều này với định nghĩa về cây nhị phân ở đây, sẽ dễ thấy được rằng danh sách có thể được xem như cây khi mỗi điểm nút chỉ có một cây con.

Một danh sách như [1,2,3] có thể được viết là 1:2:3:[]. Nó bao gồm phần tử đầu danh sách, vốn bằng 1 tiếp theo bởi phần đuôi danh sách, tức là 2:3:[]. Đến lượt mình, 2:3:[] cũng có phần tử đầu, 2 và một phần đuôi, 3:[]. Với 3:[], phần tử đầu là 3 còn phần đuôi là danh sách rỗng, [].

Ta hãy lập nên khóa kéo cho danh sách. Để chuyển mục tiêu đến danh sách con của một danh sách, ta sẽ di chuyển tiến hoặc lui (còn đối với cây thì di chuyển lên, qua trái, hoặc qua phải). Phần được chú ý (mục tiêu) sẽ là một cây con và cùng với nó ta sẽ để lại những vụn bánh trong quá trình tiến bước. Bây giờ, đối với danh sách, thì từng mẩu vụn bánh sẽ có chứa gì? Khi còn thao tác với cây nhị phân, ta đã nói rằng một mẩu vụn bánh phải chứa phần tử ở gốc của cây mẹ, cùng với tất cả những cây con mà ta đã không lựa chọn; và cũng ghi nhớ lại hướng ta đi sang trái hoặc phải. Như vậy, nó phải có tất cả những thông tin mà một điểm nút cần có, ngoại trừ cây con được ta chọn làm mục tiêu.

Danh sách thì đơn giản hơn cây, vì vậy ta không phải nhớ là ta đã đi sang trái hoặc phải, vì chỉ có một cách để đi sâu vào danh sách. Bởi mỗi nút chỉ có một cây con, nên ta cũng không phải nhớ đường đi đã chọn. Dường như điều cần nhớ chỉ là phần tử liền trước. Nếu có một danh sách như [3,4,5] và ta biết rằng phần tử liền trước là 2, thì ta có thể quay ngược lại bằng cách đơn giản là đặt phần tử đó lên đầu danh sách hiện có, và thu được [2,3,4,5].

Vì một mẩu vụn bánh ở đây chính là một phần tử, nên ta không cần phải đặt nó vào trong một kiểu dữ liệu, như ta đã làm khi lập kiểu dữ liệu Crumb cho khóa kéo áp dụng đối với cây:

type ListZipper a = ([a],[a])

Danh sách thứ nhất biểu diễn cho danh sách mà ta đang tập trung xem xét, còn danh sách thứ hai là danh sách chứa các vụn bánh. Ta hãy lập các hàm để đi tiến và lùi đối với danh sách:

goForward :: ListZipper a -> ListZipper a
goForward (x:xs, bs) = (xs, x:bs)

goBack :: ListZipper a -> ListZipper a
goBack (xs, b:bs) = (b:xs, bs)

Khi đi tiến, ta tập trung mục tiêu vào phần đuôi của danh sách hiện tại đồng thời để lại phần tử đầu danh sách với vai trò vụn bánh chỉ đường. Khi đi lùi, ta lấy mẩu vụn bánh gần nhất và đặt nó lên đầu của danh sách.

Sau đây là hai hàm số khi hoạt động:

ghci> let xs = [1,2,3,4]
ghci> goForward (xs,[])
([2,3,4],[1])
ghci> goForward ([2,3,4],[1])
([3,4],[2,1])
ghci> goForward ([3,4],[2,1])
([4],[3,2,1])
ghci> goBack ([4],[3,2,1])
([3,4],[2,1])

Ta thấy rằng với trường hợp danh sách, vụn bánh là một phần đảo ngược của danh sách, không hơn không kém. Phần tử mà ta di chuyển khỏi luôn được đứng đầu (danh sách) vụn bánh, vì vậy thật dễ dàng đi ngược lại bằng cách lấy phần tử đó ra khỏi vị trí đầu của vụn bánh và làm cho nó trở thành phần tử đầu của mục tiêu mà ta xét.

Điều này cũng giúp ta dễ thấy hơn lý do mà ta gọi cấu trúc dữ liệu này là khóa kéo, vì thực sự nó giống như bàn trượt của khóa kéo khi được kéo lên và xuống.

Nếu phải lập nên một trình soạn thảo, thì bạn có thể dùng một danh sách các chuỗi kí tự để biểu diễn các dòng chữ đang được hiện ra và sau đó có thể dùng một khóa kéo để có thể biết được con trỏ đang chạy trên dòng nào. Bằng việc dùng một khóa kéo, sẽ dễ chèn thêm các dòng mới vào bất cứ vị trí nào trong văn bản cũng như xóa bỏ các dòng đã có.

Một hệ thống tập tin rất đơn giản

Bây giờ khi ta đã biết cách hoạt động của khóa kéo rồi, ta hãy dùng cây để biểu diễn một hệ thống tập tin rất đơn giản, rồi sau đó dùng một khóa kéo cho hệ thống tập tin đó, trong đó ta được phép di chuyển giữa các thư mục, cũng như ta thường di chuyển trong hệ thống tập tin trong máy.

Với một cái nhìn đơn giản về hệ thống tập tin theo hình thức thừa kế, ta thấy rằng nó hầu như được tạo nên từ các tập tin và thư mục. Tập tin là những đơn vị dữ liệu và được đặt một cái tên, còn thư mục được dùng để tổ chức các tập tin như vậy và có thể chứa tập tin hoặc các thư mục khác. Vậy hãy coi như một phần tử trong hệ thống tập tin hoặc là một tập tin, với một tên gọi cùng dữ liệu, hoặc một thư mục, cũng với tên và một nhóm các thứ khác, có thể là tập tin hoặc bản thân các thư mục. Sau đây là một kiểu dữ liệu cho nó cùng các kiểu tương đồng, để ta dễ bề phân biệt:

type Name = String
type Data = String
data FSItem = File Name Data | Folder Name [FSItem] deriving (Show)

Một tập tin có hai chuỗi kí tự đi kèm, một để biểu diễn cho tên gọi và một cho dữ liệu chứa trong tập tin đó. Một thư mục có kèm theo mỗi chuỗi kí tự làm tên gọi và một danh sách các phần tử. Nếu như danh sách đó rỗng thì ta có một thư mục rỗng.

Sau đây là một thư mục chứa vài tập tin và thư mục con:

myDisk :: FSItem
myDisk =
    Folder "root" 
        [ File "goat_yelling_like_man.wmv" "baaaaaa"
        , File "pope_time.avi" "god bless"
        , Folder "pics"
            [ File "ape_throwing_up.jpg" "bleargh"
            , File "watermelon_smash.gif" "smash!!"
            , File "skull_man(scary).bmp" "Yikes!"
            ]
        , File "dijon_poupon.doc" "best mustard"
        , Folder "programs"
            [ File "fartwizard.exe" "10gotofart"
            , File "owl_bandit.dmg" "mov eax, h00t"
            , File "not_a_virus.exe" "really not a virus"
            , Folder "source code"
                [ File "best_hs_prog.hs" "main = print (fix error)"
                , File "random.hs" "main = print 4"
                ]
            ]
        ]

Đó là những gì mà ổ đĩa máy tính tôi đang có.

Khóa kéo cho hệ thống tập tin của ta

spongedisk

Bây giờ khi ta có một hệ thống tập tin, tất cả những gì ta cần là một khóa kéo để có thể kéo và chạy vòng quanh, rồi có thể bổ sung, thay đổi và xóa các tập tin cũng như thư mục. Giống với các cây nhị phân và danh sách, ta sẽ rải những mẩu vụn bánh có chứa thông tin về những nơi ta quyết định không thăm đến. Như ta đã nói, một mẩu vụn bánh phải có nội dung giống như một điểm nút, chỉ có điều là chứa mọi thứ ngoại trừ cây con mà ta đang hướng mục tiêu đến. Cũng cần lưu ý rằng lỗ hổng ở đâu để ngay khi đi ngược lên, thì ta có thể điền mục tiêu trước đó vào lỗ hổng này.

Ở đây, một mẩu vụn bánh sẽ giống như một thư mục, chỉ khác là nó lại thiếu mất cái thư mục mà ta đang chọn. Tại sao lại không giống một tập tin chứ, bạn có thể hỏi vậy. Ồ, vì một khi đã hướng mục tiêu vào một tập tin thì ta không thể tiến sâu hơn vào hệ thống tập tin được, vì vậy mẩu vụn bánh mì sẽ chẳng có nghĩa gì nếu dùng để đánh dấu cho tập tin cả. Một tập tin giống như một cây rỗng.

Nếu ta đang hướng mục tiêu vào thư mục "root" rồi sau đó hướng mục tiêu vào tập tin "dijon_poupon.doc" thì vụn bánh để lại sẽ trông ra sao? À, nó phải chứa tên của thư mục mẹ cùng với các phần tử đến trước tập tin mà ta hướng mục tiêu vào và những phần tử đến sau đó. Vì vậy những gì ta càn là một Name và hai danh sách chứa các phần tử. Bằng cách phân định riêng các danh sách dành cho những phần tử đến trước phần từ mục tiêu và những phần tử đến sau nó, ta đã chắc chắn phải đặt nó ở chỗ nào một khi ta di chuyển ngược lại. Vì vậy bằng cách này, ta biết được vị trí của lỗ hổng.

Sau đây là kiểu dữ liệu “vụn bánh” đối với hệ thống tập tin:
Here’s our breadcrumb type for the file system:

data FSCrumb = FSCrumb Name [FSItem] [FSItem] deriving (Show)

Vá sau đây là một kiểu tương đồng đối với khóa kéo:

type FSZipper = (FSItem, [FSCrumb])

Việc đi ngược lên trong cấu trúc thừa kế là rất đơn giản. Ta chỉ việc lấy vụn bánh gần nhất rồi lăp ghép nên mục tiêu mới từ mục tiêu hiện tại và vụn bánh, như sau:

fsUp :: FSZipper -> FSZipper
fsUp (item, FSCrumb name ls rs:bs) = (Folder name (ls ++ [item] ++ rs), bs)

Vì vụn bánh hiện có đã biết rằng tên của thư mục mẹ là gì, cũng như những phần tử đến trước phần tử mục tiêu trong thư mục (đó là ls) cùng các phần tử đến sau (đó là rs), việc đi ngược lên rất dễ dàng.

Thế còn việc đi sâu vào trong hệ thống tập tin thì sao? Nếu ta đang ở "root" và muốn đặt mục tiêu vào "dijon_poupon.doc", mẩu vụn bánh mà ta để lại sẽ có chứa tên gọi "root" cùng với những phần tử đứng trước "dijon_poupon.doc" và những phần tử đứng sau nó.

Sau đây là một hàm mà, khi cho trước một cái tên, sẽ hướng mục tiêu vào một tập tin thuộc thư mục ở trong thư mục đang được hướng mục tiêu đến:

import Data.List (break)

fsTo :: Name -> FSZipper -> FSZipper
fsTo name (Folder folderName items, bs) = 
    let (ls, item:rs) = break (nameIs name) items
    in  (item, FSCrumb folderName ls rs:bs)

nameIs :: Name -> FSItem -> Bool
nameIs name (Folder folderName _) = name == folderName
nameIs name (File fileName _) = name == fileName

fsTo nhận một tên gọi Name cùng một FSZipper rồi trả lại một FSZipper mới, trong đó hướng mục tiêu vào tập tin có tên gọi này. Tập tin đó phải nằm trong thư mục hiện đang được hướng tới. Hàm này không tìm kiếm khắp mọi nơi, mà chỉ nhìn vào thư mục hiện thời.

wow cool great

Trước hết ta dùng break để chẻ danh sách các phần tử trong một thư mục, thành những thứ đi trước tập tin cần tìm và những thứ đi sau nó. Nếu bạn còn nhớ, break nhận một vị từ cùng một danh sách rồi trả lại một cặp các danh sách. Danh sách thứ nhất trong cặp chứa những phần tử mà đối với chúng vị từ trả lại False. Tiếp theo, một khi vị từ trả lại True đối với phần tử nào, thì hàm sẽ đặt phần tử này cùng với phần còn lại của danh sách vào trong phần tử thứ hai của cặp. Ta đã lập một hàm phụ trợ có tên nameIs để nhận một tên gọi cùng một phần tử hệ thống tập tin rồi trả lại True nếu các tên gọi trùng nhau.

Như vậy, bây giờ ls là một danh sách có chứa những phần tử đứng trước phần tử mà ta cần tìm, item chính là phần tử đó, và rs là danh sách các phần tử đứng sau phần tử này trong thư mục. Bây giờ khi biết được điều này, ta chỉ việc biểu diễn phần tử, được lấy từ break, làm mục tiêu và dựng nên một đối tượng vụn bánh chứa tất cả những dữ liệu cần thiết.

Lưu ý rằng nếu tên gọi mà ta cần tìm không có trong thư mục, thì dạng mẫu item:rs sẽ thử khớp với một danh sách rỗng và ta sẽ nhận được lỗi. Ngoài ra, nếu mục tiêu hiện tại không phải là thư mục mà là một tập tin, thì ta cũng nhận được một lỗi và chương trình bị đổ vỡ.

Bây giờ ta có thể di chuyển lên xuống trong hệ thống tập tin. Hãy bắt đầu ở điểm gốc rồi đi đến tập tin "skull_man(scary).bmp":

ghci> let newFocus = (myDisk,[]) -: fsTo "pics" -: fsTo "skull_man(scary).bmp"

Bây giờ newFocus là một khóa kéo được tập trung hướng vào tập tin "skull_man(scary).bmp". Trước hết ta hãy lấy phần tử đầu tiên của khóa kéo (bản thân mục iteu) và xem liệu điều này có đúng thật sự không:

ghci> fst newFocus
File "skull_man(scary).bmp" "Yikes!"

Hãy di chuyển lên và hướng mục tiêu vào tập tin cạnh đó, "watermelon_smash.gif":

ghci> let newFocus2 = newFocus -: fsUp -: fsTo "watermelon_smash.gif"
ghci> fst newFocus2
File "watermelon_smash.gif" "smash!!"

Thao tác với hệ thống tập tin mới lập

Bây giờ khi đã biết cách di chuyển trong hệ thống tập tin, việc thao tác trên nó cũng dễ dàng. Sau đây là một hàm để đổi tên tập tin hoặc thư mục được hướng mục tiêu đến:

fsRename :: Name -> FSZipper -> FSZipper
fsRename newName (Folder name items, bs) = (Folder newName items, bs)
fsRename newName (File name dat, bs) = (File newName dat, bs)

Bây giờ ta có thể đổi tên thư mục "pics" thành "cspi":

ghci> let newFocus = (myDisk,[]) -: fsTo "pics" -: fsRename "cspi" -: fsUp

Ta hạ xuống thư mục "pics", đổi tên nó rồi đi ngược trở lên.

Thế còn một hàm để tạo ra phần tử mới trong thư mục hiện tại thì sao? Hãy xem này:

fsNewFile :: FSItem -> FSZipper -> FSZipper
fsNewFile item (Folder folderName items, bs) = 
    (Folder folderName (item:items), bs)

Dễ như ăn bánh vậy. Lưu ý rằng mã lệnh trên có thể đổ vỡ nếu ta thêm vào một phần tử nhưng lại không hướng mục tiêu vào một thư mục mà vào một tập tin.

Ta hãy bổ sung một tập tin vào thư mục "pics" rồi di chuyển ngược lên điểm gốc:

ghci> let newFocus = (myDisk,[]) -: fsTo "pics" -: fsNewFile (File "heh.jpg" "lol") -: fsUp

Cách này hay ở chỗ là khi ta sửa đổi hệ thống tập tin, nó thực sự không thao tác sửa đổi trên ngay hệ thống hiện tại mà trả lại một hệ thống tập tin hoàn toàn mới. Bằng cách đó, ta có quyền truy cập vào hệ thống tập tin cũ (trong trường hợp này là myDisk) cũng như hệ thống mới (thành phần thứ nhất của newFocus). Như vậy bằng việc dùng khóa kéo, tự nhiên ta lại được cơ chế lưu trữ phiên bản; theo nghĩa là ta luôn có thể tham khảo các bản cũ hơn của cấu trúc dữ liệu ngay cả khi ta đã thay đổi nó. Điều này không phải đặc tính riêng của khóa kéo, mà là một thuộc tính của Haskell vì các cấu trúc dữ liệu của nó có tính bất biến. Tuy nhiên với khóa kéo, ta có được khả năng di chuyển quanh cấu trúc dữ liệu dễ dàng và hiệu quả, như vậy tính duy trì của các cấu trúc dữ liệu trong Haskell bắt đầu phát huy tác dụng.

Hãy bước đi cẩn thận

Đến giờ, khi đi trong cơ sở dữ liệu ta đã lập, dù chúng là cây nhị phân, danh sách hay hệ thống tập tin, ta không bận tâm ngay cả nếu có lỡ bước quá và trượt chân. Chẳng hạn, hàm goLeft nhận một khóa kéo của một cây nhị phân rồi chuyển mục tiêu đến cây con bên trái của nó:

goLeft :: Zipper a -> Zipper a
goLeft (Node x l r, bs) = (l, LeftCrumb x r:bs)

falling for you

Nhưng sẽ ra sao nếu như cây mà ta vừa trượt chân là một cây rỗng? Nghĩa là, sẽ thế nào nếu nó không phải là một Node, mà là Empty? Trong trường hợp này, ta sẽ nhận một lỗi thực thi vì phép khớp mẫu sẽ thất bại và ta không có dạng mẫu nào để xử lý trường hợp cây rỗng, tức là cây không có cây con nào. Đến giờ, ta mới chỉ giả sử rằng ta không bao giờ hướng mục tiêu vào cây con bên trái của một cây rỗng khi cây con bên trái của nó không hề tồn tại. Nhưng việc đi vào cây con trái của một cây rỗng không có ý nghĩa gì, nên đến giờ ta tiện tay bỏ qua nó.

Hoặc sẽ ra sao nếu ta đã ở gốc một cây nào đó và không có vụn bánh nào nhưng vẫn cố gắng đi lên? Điều tương tự sẽ xảy ra. Dường như là khi dùng khóa kéo, bất kì bước đi nào cũng có thể là bước đi cuối cùng. Nói cách khác, bất kì bước đi nào cũng có thể dẫn đến thành công, nhưng cũng có thể thất bại. Điều này có gợi cho bạn gì không? Dĩ nhiên rồi, monad! Cụ thể hơn, đó chính là monad Maybe, có tác dụng bổ sung một ngữ cảnh có khả năng thất bại vào cho những giá trị thông thường.

Vậy ta hãy dùng monad Maybe để bổ sung một ngữ cảnh thất bại vào cho những hoạt động hiện có. Ta sẽ lấy các hàm hoạt động với khóa kéo cây nhị phân vừa lập và sẽ biến chúng thành các hàm monad. Trước hết, hãy xử lý thất bại có thể xảy ra ở goLeftgoRight. Cho đến giờ, sự thất bại của các hàm có khả năng thất bại đều luôn được phản ánh trong kết quả của chúng, và lần này không phải ngoại lệ. Như vậy sau đây sẽ là goLeftgoRight với thêm khả năng cho thất bại xảy ra.

goLeft :: Zipper a -> Maybe (Zipper a)
goLeft (Node x l r, bs) = Just (l, LeftCrumb x r:bs)
goLeft (Empty, _) = Nothing

goRight :: Zipper a -> Maybe (Zipper a)
goRight (Node x l r, bs) = Just (r, RightCrumb x l:bs)
goRight (Empty, _) = Nothing

Thật hay, bây giờ nếu ta cố thử đi một bước về bên trái của cây rỗng, ta sẽ nhận được Nothing!

ghci> goLeft (Empty, [])
Nothing
ghci> goLeft (Node 'A' Empty Empty, [])
Just (Empty,[LeftCrumb 'A' Empty])

Trông có vẻ tốt đấy! Vậy còn đi lên trên? Vấn đề trước đây đã xảy ra nếu ta cố đi lên nhưng không còn vụn bánh nữa, nghĩa là ta đã ở gốc của cây. Sau đây là hàm goUp để tung ra một lỗi nếu ta vượt ngoài khuôn khổ của cây:

goUp :: Zipper a -> Zipper a
goUp (t, LeftCrumb x r:bs) = (Node x t r, bs)
goUp (t, RightCrumb x l:bs) = (Node x l t, bs)

Bây giờ hãy sửa đổi mã lệnh để nếu có thất bại thì hãy làm theo cách thật lịch thiệp:

goUp :: Zipper a -> Maybe (Zipper a)
goUp (t, LeftCrumb x r:bs) = Just (Node x t r, bs)
goUp (t, RightCrumb x l:bs) = Just (Node x l t, bs)
goUp (_, []) = Nothing

Nếu có vụn bánh, mọi việc sẽ ổn thỏa và ta trả lại một mục tiêu thành công mới, nhưng nếu không, thì ta trả lại một thất bại.

Trước đây, các hàm này nhận khóa kéo và cũng trả lại khóa kéo, có nghĩa là ta có thể xâu chuỗi chúng như sau trong quá trình đi trên cấu trúc dữ liệu:

gchi> let newFocus = (freeTree,[]) -: goLeft -: goRight

Nhưng bây giờ, thay vì trả lại Zipper a, chúng trả lại Maybe (Zipper a), vì vậy xâu chuỗi các hàm như vậy không còn tác dụng nữa. Ta đã gặp vấn đề tương tự khi xử lý với người thăng bằng trên dây ở chương nói về monad. Anh ta cũng bước từng bước một và mỗi bước đi có thể dẫn đến thất bại vì một bầy chim có thể đậu xuống một đầu cây sào thăng bằng làm anh ta té ngã.

Bây giờ, trò đùa lại hướng về chúng ta vì bây giờ chính ta là người đi, dò dẫm trong mê cung của sản phẩm (cấu trúc dữ liệu) vừa chế ra. Thật may, ta có thể học theo người đi dây và chỉ việc làm theo những gì anh ta làm, tức là tráo đổi việc áp dụng hàm thông thường bằng >>=, vốn nhận vào một giá trị cùng ngữ cảnh (ở trường hợp này là Maybe (Zipper a), với ngữ cảnh của thất bại có thể) rồi đưa nó vào trong một hàm trong khi vẫn đảm bảo rằng ngữ cảnh này được theo dõi cẩn thận. Như vậy cũng giống với người đi dây, ta sẽ đánh đổi toàn bộ những toán tử -: bằng >>=. Được rồi, ta lại có thể xâu chuỗi các hàm hiện có một lần nữa! Xem này:

ghci> let coolTree = Node 1 Empty (Node 3 Empty Empty)
ghci> return (coolTree,[]) >>= goRight
Just (Node 3 Empty Empty,[RightCrumb 1 Empty])
ghci> return (coolTree,[]) >>= goRight >>= goRight
Just (Empty,[RightCrumb 3 Empty,RightCrumb 1 Empty])
ghci> return (coolTree,[]) >>= goRight >>= goRight >>= goRight
Nothing

Ta đã dùng return để đặt một khóa kéo vào trong một Just rồi dùng >>= để đưa nó vào trong hàm goRight. Trước hết, ta lập nên một cây mà bên trái của nó có một cây con rỗng và bên phải là một điểm nút với hai cây con rỗng. Khi ta cố gắng đi sang phải một lần, kết quả là thành công, vì thao tác này có ý nghĩa. Việc sang phải hai lần cũng ổn; cuối cùng ta có mục tiêu hướng đến một cây con rỗng. Nhưng nếu đi sang phải ba lần sẽ không có nghĩa rồi, vì ta không thể sang phải một cây con rỗng được, bởi vậy mà kết quả là một Nothing.

Bây giờ ta đã trang bị lưới an toàn cho những cây mới dựng nên, để có thể đỡ được ta nếu chẳng may ngã. Oah, vậy là tôi đã là người phát kiến ra phép ẩn dụ này.

Hệ thống tập tin của ta cũng có nhiều trường hợp trong đó thao tác có thể thất bại, chẳng hạn như cố gắng hướng mục tiêu đến một tập tin hoặc thư mục khong tồn tại. Bạn hãy tự làm bài tập này, hãy trang bị cho hệ thống tập tin vừa lập với các hàm có biểu hiện lịch thiệp khi thất bại, qua việc dùng monad Maybe.

Advertisements

1 phản hồi

Filed under Haskell

One response to “Chương 14: Khóa kéo

  1. Pingback: Tự học lấy Haskell | Blog của Chiến

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s