StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I guess the first Int of Graph is a bound for your nodes (like, 6 if the nodes are in <code>[1..6]</code>).</p> <p>Therefore, you would like a function that returns the triangles of a graph, so the type might be:</p> <pre><code>triangles :: Graph -> [(Int, Int, Int)] </code></pre> <p>Now, a triangle exists whenever, for 3 nodes, say <code>x</code> <code>y</code> and <code>z</code>, all the combinations return <code>True</code> through <code>g</code>.</p> <p>So, you might want to consider generating all these combinations (possibly avoiding the ones that are equivalent via re-ordering), and filter out only those that validate the criterion:</p> <pre><code>isTriangle :: Graph -> (Int, Int, Int) -> Bool isTriangle (_, g) (x, y, z) == g x y && g y z && g x z </code></pre> <p>For this, you could use a <a href="http://haskell.org/haskellwiki/List_comprehension" rel="nofollow">list comprehension</a>, or the function <a href="http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v%3afilter" rel="nofollow">filter</a> which has type <code>(a -> Bool) -> [a] -> [a]</code></p> <hr> <p>Answer to your first comment:</p> <p>First, you would need to implement the <code>triangles</code> function, which is the reason of the error. But, as you have done in <code>test</code>, you could simply generate these triangles on the fly.</p> <p>Now, you wrote:</p> <pre><code>test = filter (isTriangle) [(x,y,z) | x <- [1..3], y <- [1..3], z <- [1..3]] </code></pre> <p>Two things about this:</p> <ul> <li>First, you wouldn't need the parentheses around <code>isTriangle</code> for what you wrote, but it is incorrect, since <code>isTriangle</code> expects a graph as its first parameter</li> <li><p>Second, you are going to obtain a lot of duplicates, and if you want, you can prevent this by not generating them in the first place:</p> <pre><code>test = filter (isTriangle) [(x,y,z) | x <- [1..3], y <- [1..x], z <- [1..y]] </code></pre></li> </ul> <p>Alternatively, you can dismiss the <code>filter</code> function by providing a guard in the list comprehension syntax, as this:</p> <pre><code>[(x, y, z) | x <- [1..3], y <- [1..x], z <- [1..y], isTriangle yourGraph (x, y, z)] </code></pre> <p>Now, I'll let you go on with the details. You will want to make this a function that takes a graph, and to replace this <code>3</code> by the number of nodes in the graph, and yourGraph by said graph.</p> <p>Since you chose to use list comprehension, forget about the generating function that I wrote about earlier, its purpose was just to generate input for <code>filter</code>, but with the list comprehension approach you won't necessarily need it.</p> <hr> <p>Answer to your second comment:</p> <p>You want to write a function:</p> <pre><code>triangles :: Graph -> [(Int, Int, Int)] triangles (n, g) = [(x, y, z) | ...] </code></pre> <p>The <code>...</code> are to be replaced with the correct things, from earlier (ranges for x, y and z, as well as the predicate isTriangle).</p> <p>Alternatively, you can cut this in two functions:</p> <pre><code>allTriangles :: Int -> [(Int, Int, Int)] allTriangles n = [(x, y, z) | ...] graphTriangles :: Graph -> [(Int, Int, Int)] graphTriangles (n, g) = [t | t <- allTriangles n, isGraphTriangle t] where isGraphTriangle (x, y, z) = ... </code></pre> <p>This way, you could potentially reuse <code>allTriangles</code> for something else. If you don't feel the need, you can stay with the one-shot big comprehension <code>triangles</code>, since it's a homework you probably won't build up on it.</p> <p>I try not to fill all the <code>...</code> so that you can do it yourself and hopefully understand :)</p> <hr> <p>Correcting your solution:</p> <p>First, my mistake on the ranges, it should be <code>x <- [1..n], y <- [x+1..n], z <- [y+1..n]</code> where <code>n</code> denotes the number of nodes in your graph. This way, you only capture triples where <code>x < y < z</code>, which ensures that you only see one occurence of each set of three points.</p> <p>Second, the reason why I put the graph as a parameter to the functions is that you might want to reuse the same function for another graph. By hardcoding <code>g</code> and <code>6</code> in your functions, you make them really specific to the particular graph you described, but if you want to compute <code>triangles</code> on a certain number of graphs, you do not want to write one function per graph!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload