haskell - zipper - use examples: file system and watch the steps

we have seen the zipper in the previous post, now we will see some application and examples of Zippers. 

 

firt, we will examine a simple file system implemented with Zipper. 

 

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

 

to help understanding and experimenting the file system with we will create the following example folder structure. 

 

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"  
                ]  
            ]  
        ]  

 

As usual we will create the breadcrumbs to leave us a trail of info that helps us to construct info when we navigate up and down the system . 

 

Here's our breadcrumb type for the file system .

 

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

 

and here is our type synonyms of our zipper 

type FSZipper = (FSItem, [FSCrumb])  

 you may wonder why the FSCrumb is like this, the name is for the name of the parent folder, and the first [FSItem] is for the items before the currently focused item, and the ensuing [FSItem] is the collection of items that comes after the current item. 

 

with this piece of information, we can going back in the hierarchy very easily, we just make the latest breadcrumb and assembles a  new focus from the current focus and breadcrubm, like so:

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

 

and if you want to go deeper into the file system, if you are in the "root" and we want to focus on the "dijon_poupon.doc" . the breadcrub that we leaves is going to include the name "root" along with the items that precede "dijon_poupon.doc" and teh ones that comes after it. 

 

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  

 

First we use break to break the list of items in a folder into those that precede the file that we're searching for and those that come after it. If you remember, break takes a predicate and a list and returns a pair of lists. The first list in the pair holds items for which the predicate returns False. Then, once the predicate returns True for an item, it places that item and the rest of the list in the second item of the pair. We made an auxilliary function called nameIs that takes a name and a file system item and returns True if the names match.

 

there is limitation, of course with this simple implementation,  Note that if the name we're looking for isn't in the folder, the pattern item:rs will try to match on an empty list and we'll get an error. Also, if our current focus isn't a folder at all but a file, we get an error as well and the program crashes.

 

let's stretch our muscles. 

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

 

we can get the focus (the first component of the zipper) , and see what really it is. 

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

 

and we can also, move up and focus on the neighboring file, here it is : 

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

 

Manipulating our file system 

now we have the ability to navigate through the file system, and we want to endow our file system the ability to manipulate the files. 

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

 

to show how we can use that: , we can name our "pics" to "cspi",  

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

 

how about a function that makes a new item in the current folder, behold.

 

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

 easy as a pie. to show , suppose we add a "pics" folder and then move back up to the front. 

 

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

 What's really cool about all this is that when we modify our file system, it doesn't actually modify it in place but it returns a whole new file system. That way, we have access to our old file system (in this case, myDisk) as well as the new one (the first component of newFocus) 

 

Watch your step 

so far, while walking through our data structure, whether they were binary tree, lists or file system, we didn't really care if we took a step too far and fell off, for instance, our go left function takes a zipper of binary tree and moves the focus to its left sub-tree. 

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

 

things that we don't cover is that if we 're stepping off from is an empty tree, that is , what if it's not a Node but an empty... what we have with our current  impl is a runtime error, not some idea situation that we want.

 

we know that with Maybe, we can have a success status denoted by a Just value and a failure situation denoted by a Nothing maybe type. 

 

let's enrich the code to have the maybe code. 

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  

 

now, we won't fell off because we are going too far, instead Nothing sh ould be what we get. 

 

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

 

and we update the goUp method and we have this

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  

  

what we have in extra is the last setence, caled 

goUp (_, []) = Nothing  

 

now, instead of getting Zipper a, we are getting a Maybe type, and the type in our contex is Maybe (zipper a), but our current function takes only Zipper, so we have to trade in all our -: with >>=, alright, we can chain the operation again!, 

 

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  

 

so, we have equipped our tree with a safety-net that we will catch us should we fall off. The FileSystem we mentioned before do not have this safety-net, we might as well add it back.