Понимание простых функций, применяемых к графам

Question

У меня есть вопрос о том, как управлять функцией в Haskell. У меня есть этот график:

import Data.Map (Map,empty,member,insert)
import Graphviz
-- | A directed graph
data Graph v = Graph
    { arcsMap :: Map v [v]     -- A map associating a vertex with its successors
    , labelMap :: Map v String -- The Graphviz label of each node
    , styleMap :: Map v String -- The Graphviz style of each node
    }deriving (Show,Eq, Ord)

И у меня есть эти функции

-- | Adds a vertex to a graph
addVertex :: Ord v => v -> Graph v -> Graph v
addVertex _ (Graph arcs labels styles)= (Graph arcs labels styles)
addVertex v (Graph arcs labels styles) = Graph (insert v [] arcs) labels styles

-- | Adds vertices to a graph
addVertices :: Ord v => Graph v -> [v] -> Graph v
addVertices (Graph arcs labels styles) [v] = map addVertex [v]

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

Answer 1

Обычно это делается с помощью сгиба, например foldr :: Foldable f => (a -> b -> b) -> b -> f a -> b. Действительно, мы можем добавить элементы списка вершин (или фактически Foldable f => f элементов):

addVertices :: (Foldable f, Ord v) => Graph v -> f v -> Graph v
addVertices g0 = foldr addVertex g0

Для списка вы можете увидеть foldr как способ замены пустого списка[] с базовым элементом g0, и мы заменим все «минусы» (:) на функцию addVertex здесь. Таким образом, это означает, что для списка:

v<sub>1</sub> : v<sub>2</sub> : v<sub>3</sub> : []

или более подробного:

(:) v<sub>1</sub> ((:) v<sub>2</sub> ((:) v<sub>3</sub> []))

мы будем вычислять результат следующим образом:

addVertex v<sub>1</sub> (addVertex v<sub>2</sub> (addVertex v<sub>3</sub> g<sub>0</sub>))

и, таким образом, каждый раздобавьте одну вершину к графику.

Мы можем использовать foldl :: Foldable f => (b -> a -> b) -> b -> f a -> b вместо того, чтобы передавать аккумулятор слева направо:

addVertices :: (Foldable f, Ord v) => Graph v -> f v -> Graph v
addVertices g0 = foldl (flip addVertex) g0

Затем мы свернем список следующим образом:

addVertex v<sub>3</sub> (addVertex v<sub>2</sub> (addVertex v<sub>1</sub> g<sub>0</sub>))

Так как здесь используется Foldable, мы можем добавить вершины во все виды структур данных, например, Maybe v, [v], Tree v и т. д.

Здесь мы можем использовать η-уменьшение и реализовать такие функции как:

addVertices1 :: (Foldable f, Ord v) => Graph v -> f v -> Graph v
addVertices1 = foldr addVertex

addVertices2 :: (Foldable f, Ord v) => Graph v -> f v -> Graph v
addVertices2 = foldl (flip addVertex)