Изучай Haskell во имя добра!

Обычная иерархическая файловая система состоит преимущественно из файлов и каталогов. Файлы – это элементы данных, снабжённые именами. Каталоги используются для организации этих файлов и могут содержать файлы или другие каталоги. Для нашего простого примера достаточно сказать, что элементами файловой системы являются:

• файл под некоторым именем, содержащий некие данные;

• каталог под некоторым именем, содержащий другие элементы, которые сами являются или файлами, или каталогами.

Вот соответствующий тип данных и некоторые синонимы типов, чтобы было понятно, что к чему:

type Name = String

type Data = String

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

К файлу прилагаются две строки, представляющие его имя и содержимое. К каталогу прилагаются строка, являющаяся его именем, и список элементов. Если этот список пуст, значит, мы имеем пустой каталог.

Вот каталог с некоторыми файлами и подкаталогами (на самом деле это то, что в настоящую минуту содержится на моём диске):

myDisk :: FSItem

myDisk =

   Folder "root"

      [ File "goat_yelling_like_man.wmv" "бааааааа"

      , File "pope_time.avi" "Боже, благослови"

      , Folder "pics"

        [ File "ape_throwing_up.jpg" "блин..."

        , File "watermelon_smash.gif" "шмяк!!"

        , File "skull_man(scary).bmp" "Ой!"

        ]

      , File "dijon_poupon.doc" "лучшая горчица"

      , Folder "programs"

        [ File "sleepwizard.exe" "10 пойти поспать"

        , File "owl_bandit.dmg" "move ax, 42h"

        , File "not_a_virus.exe" "точно не вирус"

        , Folder "source code"

           [ File "best_hs_prog.hs" "main = print (fix error)"

           , File "random.hs" "main = print 4"

           ]

        ]

      ]

Создаём застёжку для нашей файловой системы

Теперь, когда у нас есть файловая система, всё, что нам нужно, – это застёжка, чтобы мы могли застёгивать файловую систему и брать её крупным планом, а также добавлять, изменять и удалять файлы и каталоги. Как и в случае с использованием бинарных деревьев и списков, наши «хлебные крошки» будут содержать информацию обо всём, что мы решили не посещать. Отдельная «хлебная крошка» должна хранить всё, кроме поддерева, на котором мы фокусируемся в данный момент. Она также должна указывать, где находится отверстие, чтобы при перемещении обратно вверх мы смогли вставить в отверстие наш предыдущий фокус.

В этом случае «хлебная крошка» должна быть похожа на каталог – только выбранный нами в данный момент каталог должен в нём отсутствовать. Вы спросите: «А почему не на файл?» Ну, потому что, когда мы фокусируемся на файле, мы не можем углубляться в файловую систему, а значит, не имеет смысла оставлять «хлебную крошку», которая говорит, что мы пришли из файла. Файл – это что-то вроде пустого дерева.

Если мы фокусируемся на каталоге "root", а затем на файле "dijon_poupon.doc", как должна выглядеть «хлебная крошка», которую мы оставляем? Она должна содержать имя своего родительского каталога вместе с элементами, идущими перед файлом, на котором мы фокусируемся, и следом за ним. Поэтому всё, что нам требуется, – значение Name и два списка элементов. Храня два отдельных списка для элементов, идущих перед элементом, на котором мы фокусируемся, и для элементов, идущих за ним, мы будем точно знать, где мы его поместили, при перемещении обратно вверх. Таким образом, нам известно местоположение отверстия.

Вот наш тип «хлебной крошки» для файловой системы:

data FSCrumb = FSCrumb Name [FSItem] [FSItem]

deriving (Show)

А вот синоним типа для нашей застёжки:

type FSZipper = (FSItem, [FSCrumb])

Идти обратно вверх по иерархии очень просто. Мы берём самую последнюю «хлебную крошку» и собираем новый фокус из текущего фокуса и «хлебной крошки» следующим образом:

fsUp :: FSZipper –> FSZipper

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

Поскольку нашей «хлебной крошке» были известны имя родительского каталога, а также элементы, которые шли перед находящимся в фокусе элементом каталога (то есть ls), и элементы, которые шли за ним (то есть rs), перемещаться вверх было легко.