Как лениво загрузить DataTypes кроме списков в Haskell

Question

Я начинаю понимать силу Haskell и то, как ленивая загрузка может быть использована такими способами, как

main = do
  s <- getContents
  let r = map processIt (lines s)
  putStr (unlines r)

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

Например, у меня есть тип графика.

type Key = String
data Node = Node { key :: Key, links :: [Node] }

Я хочу написать чистый код, который действует на этом графике (алгоритмы прямого поиска), независимо от того, как он построен, но я хочу, чтобы узлы лениво заполнялись, когда я к ним добирался.

Я думаю, что мне нужен способ заранее указать, что находится на графике и как его заполнить (какое-то рекурсивное определение), но мне сложно понять, как это сделать. Что-то вроде

loadGraph :: Key -> Node
loadGraph k =
  let (key,edges) = getNodeAndEdgesFromInternetOrDatabase k in
  Node key (map loadGraph edges)

Я чувствую, что это близко, но я не совсем уверен, как это сделать. Помощь и советы будут оценены. (особенно такие вещи, как тип getNodeAndEdgesFromInternetOrDatabase)

Answer 1

Ленивый ввод-вывод обычно реализуется с использованием unsafeInterleaveIO, который задерживает побочные эффекты действия IO до тех пор, пока не потребуется его результат.

Для вашего примера это будет примерно так.

loadGraph :: Key -> IO Node
loadGraph k = unsafeInterleaveIO $ do
  (key, edges) <- getNodeAndEdgesFromInternetOrDatabase k
  edges' <- mapM loadGraph edges
  return (Node key edges')

Поскольку unsafeInterleaveIO переносит каждый вызов на loadGraph, этот подграф будет загружаться только при попытке его оценки.

Некоторые считают, что ленивый ввод-вывод недоволен, так как это затрудняет анализ порядка возникновения побочных эффектов. Тем не менее, я думаю, что для вашего приложения это может подойти, если вы будете осторожны с реализацией getNodeAndEdgesFromInternetOrDatabase.