https://wiki.haskell.org/index.php?title=99_questions/Solutions/80&feed=atom&action=history
99 questions/Solutions/80 - Revision history
2024-03-28T20:12:36Z
Revision history for this page on the wiki
MediaWiki 1.35.5
https://wiki.haskell.org/index.php?title=99_questions/Solutions/80&diff=61402&oldid=prev
Wizzup: categorize
2017-01-10T03:48:52Z
<p>categorize</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 03:48, 10 January 2017</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 54:</td>
<td colspan="2" class="diff-lineno">Line 54:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>friToAdj = graphToAdj . friToGraph</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>friToAdj = graphToAdj . friToGraph</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Programming exercise spoilers]]</div></td>
</tr>
</table>
Wizzup
https://wiki.haskell.org/index.php?title=99_questions/Solutions/80&diff=57135&oldid=prev
Vict: created page w/ working solution
2013-11-22T19:29:36Z
<p>created page w/ working solution</p>
<p><b>New page</b></p><div>(***) Conversions<br />
<br />
Write predicates to convert between the different graph representations.<br />
<br />
Here is a working solution for the graph-term, adjacency-list, and edge-clause / human-friendly forms for undirected, unweighted graphs.<br />
<br />
<haskell><br />
data Graph a = Graph [a] [(a, a)]<br />
deriving (Show, Eq)<br />
<br />
data Adjacency a = Adj [(a, [a])]<br />
deriving (Show, Eq)<br />
<br />
data Friendly a = Edge [(a, a)]<br />
deriving (Show, Eq)<br />
<br />
graphToAdj :: (Eq a) => Graph a -> Adjacency a<br />
graphToAdj (Graph [] _) = Adj []<br />
graphToAdj (Graph (x:xs) ys) = Adj ((x, ys >>= f) : zs)<br />
where <br />
f (a, b) <br />
| a == x = [b]<br />
| b == x = [a]<br />
| otherwise = []<br />
Adj zs = graphToAdj (Graph xs ys)<br />
<br />
adjToGraph :: (Eq a) => Adjacency a -> Graph a<br />
adjToGraph (Adj []) = Graph [] []<br />
adjToGraph (Adj ((v, a):vs)) = Graph (v : xs) ((a >>= f) ++ ys)<br />
where<br />
f x = if (v, x) `elem` ys || (x, v) `elem` ys<br />
then []<br />
else [(v, x)]<br />
Graph xs ys = adjToGraph (Adj vs)<br />
<br />
graphToFri :: (Eq a) => Graph a -> Friendly a<br />
graphToFri (Graph [] _) = Edge []<br />
graphToFri (Graph xs ys) = Edge (ys ++ zip g g)<br />
where<br />
g = filter (\x -> all (\(a, b) -> x /= a && x /= b) ys) xs<br />
<br />
friToGraph :: (Eq a) => Friendly a -> Graph a<br />
friToGraph (Edge []) = Graph [] []<br />
friToGraph (Edge vs) = Graph xs ys<br />
where<br />
xs = foldr acc [] $ concat $ map (\(a, b) -> [a, b]) vs<br />
ys = filter (uncurry (/=)) vs<br />
acc x xs = if x `elem` xs then xs else x : xs<br />
<br />
adjToFri :: (Eq a) => Adjacency a -> Friendly a<br />
adjToFri = graphToFri . adjToGraph<br />
<br />
friToAdj :: (Eq a) => Friendly a -> Adjacency a<br />
friToAdj = graphToAdj . friToGraph<br />
</haskell></div>
Vict