Блог

Я пытаюсь разобраться с Haskell, и я нашел несколько семинаров, в которых предлагается создать структуру данных графа. Я последовал примеру и создал двоичное дерево, используя map, что было намного проще. У меня есть следующие типы данных

 type Graph a = [(Node a, Edges)]

type Edges = [NodeID]

type NodeID = Int

data Node a = Node
  { getNodeID :: NodeID,
    getNodeVal :: a
  }
  deriving (Show, Eq)
  

и пример узла будет следующим

 nodeA = Node 0 'A'
  

и пример графа, связанного в обоих направлениях, будет

 graphA = [(nodeA, [1]), nodeB, [0]]
  

Теперь, чтобы выполнить какую-либо операцию вставки или удаления, мне сначала нужно было бы выяснить, каков максимальный NodeID на данный момент. Итак, я пытаюсь написать maxNodeID следующим образом

 maxNodeID :: Graph a -> Maybe NodeID
maxNodeID [] = Nothing --base case
  

Но мне очень сложно придумать следующий вариант для этой функции.

Мое определение типа для функции insertNode выглядит следующим образом

 insertNode :: a -> Graph a -> Graph a
-- This is my idea for a base case but I get a parse error at 0  
insertNode v [] = [a, []] where a = Node {0, v}  
  

Любая помощь в этом и создании функции insertNode была бы очень признательна, поскольку это действительно помогло бы мне встать на правильный путь.

Вместо того, чтобы создавать свою собственную, я бы использовал maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a функцию из Data.List .

 maxNodeID :: Graph a -> Maybe NodeID
maxNodeID [] = Nothing --base case
maxNodeID xs = Just $ maximumBy (a b -> compare (getID a) (getID b)) xs
  where getID = getNodeID . fst
  

Для вашей insertNode функции вам нужно

 insertNode v [] = [(a, [])] where a = Node 0 v
-- or --
insertNode v [] = [(a, [])] where a = Node {getNodeID = 0, getNodeVal= v}
  

Отредактировано для добавления:

Если вам еще не знакомы классы типов, вы можете прочитать тип maximumBy specialized для списков как :: (a -> a -> Ordering) -> [a] -> a .