Haskell — молнии

Молния в Haskell — это, в основном, указатели, указывающие на определенное расположение структуры данных, такой как дерево .

Давайте рассмотрим дерево, имеющее 5 элементов [45,7,55,120,56], которые можно представить в виде идеального бинарного дерева. Если я хочу обновить последний элемент этого списка, то мне нужно пройти через все элементы, чтобы добраться до последнего элемента, прежде чем обновлять его. Правильно?

Но что, если бы мы могли построить наше дерево таким образом, чтобы дерево с N элементами было набором из [(N-1), N] . Тогда нам не нужно проходить через все нежелательные (N-1) элементы. Мы можем напрямую обновить N-й элемент. Это именно концепция молния. Он фокусируется или указывает на конкретное местоположение дерева, где мы можем обновить это значение, не пересекая все дерево.

В следующем примере мы реализовали концепцию Zipper в списке. Таким же образом можно реализовать Zipper в виде дерева или файловой структуры данных.

Live Demo

data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)
type Zipper_List a = ([a],[a])    

go_Forward :: Zipper_List a -> Zipper_List a   
go_Forward (x:xs, bs) = (xs, x:bs)   
   
go_Back :: Zipper_List a -> Zipper_List a   
go_Back (xs, b:bs) = (b:xs, bs)    

main = do 
   let list_Ex = [1,2,3,4] 
   print(go_Forward (list_Ex,[]))       
   print(go_Back([4],[3,2,1])) 

([2,3,4],[1]) 
([3,4],[2,1])