Loop a function 10 times in Haskell

Question

Do you have any idea how I can loop the function func2 10 times

type Vertex = Int
type OutNeighbors = [Vertex]
data Graph = Graph [(Vertex,OutNeighbors)] deriving (Eq, Show, Read)

func2 (Graph g) = filter (\x -> contains (fst x) (func1 (Graph g))) g   --I need to repeat this function 10 times.

I am kind of new to haskell and I have no idea how to do loops

Answer 1

Do you have any idea how I can loop the function func2 10 times

You could iterate it and !! at 10:

> take 5 $ iterate ("hi " ++) "there!"
["there!","hi there!","hi hi there!","hi hi hi there!","hi hi hi hi there!"]

> let func2 = (+3) in iterate func2 0 !! 10
30

but that would require func2 to return the same type as its input, and right now it appears to have type

func2 :: Graph -> [(Vertex,OutNeighbors)]

But if you wrapped Graph back onto it, i.e.,

func2 :: Graph -> Graph
func2 (Graph g) = Graph (... g)

then you could iterate on it.

Answer 2

In Haskell you can use recursion for loops, here is an example:

myLoop 0 g = g
myLoop n g = myLoop (n - 1) (Graph (func2 g))

Now calling myLoop 10 g will call func2 10 times on g.

Note that I had to wrap the result back in the Graph type, that is probably something you should do in the func2 function:

func2 (Graph g) = Graph (filter (\x -> contains (fst x) (func1 (Graph g))) g)

You can get a little bit higher-level if you wrap this up in the State monad from the transformers package:

import Control.Monad.Trans.State.Lazy (execState, modify)
import Control.Monad (replicateM_)

myLoop :: Int -> Graph -> Graph
myLoop n g = execState (replicateM_ n (modify func2)) g

Answer 3

This is one of these situations where, in order to avoid typing errors, you need to be able to refer to both the whole parameter and to its subcomponents thru proper names.

Fortunately, Haskell provides just that. This is known as the “as patterns”. More details here: SO-q30326249.

In your case, you could note your graph parameter as: g@(Graph(pairs)). Then, g is your graph object, and pairs is the corresponding list of type [(Vertex,OutNeighbors)].

You do not tell us about your contains function, but it is possible to infer that its type is:

contains :: Vertex -> Graph -> Bool

With that in mind, a version of your graph function taking an arbitrary iteration count can be written this way:

type Vertex = Int
type OutNeighbors = [Vertex]
data Graph = Graph [(Vertex,OutNeighbors)]  deriving  (Eq, Show, Read)

funcN :: Int -> Graph -> Graph
funcN  iterCount  g@(Graph(pairs)) =
    if (iterCount <= 0)  then  g  -- nothing to do
                         else  let
                                   gm1 = funcN (iterCount - 1) g     -- recursion
                                   fn  = \(v,ngs) -> contains v gm1  -- filtration
                               in
                                   Graph (filter fn pairs)

Using the same techniques, a tentative version of the contains function could be like this:

contains :: Vertex -> Graph -> Bool
contains v g@( Graph [] )                 =  False
contains v g@( Graph ((v0,ngs0):pairs) )  =  (v == v0)  ||  contains v (Graph(pairs))

This second function is a bit more complicated, because lists can be described thru 2 patterns, empty and non-empty.

Finally, a version of the function that does exactly 10 iterations can be written like this:

func10 :: Graph -> Graph
func10 g = funcN 10 g

or also in a more concise fashion using partial application (known in Haskell circles as currying):

func10 :: Graph -> Graph
func10 = funcN 10

Addendum: library style, using nest:

If for some reason “manual recursion” is frowned upon, it is possible to use instead the nest :: Int -> (a -> a) -> a -> a library function. It computes the Nth compositional power of a function, using recursion internally.

Then one just has to write the single iteration version of the graph function. The code looks like this:

import Data.Function.HT  (nest)

funcNl :: Int -> Graph -> Graph
funcNl iterCount g0 = let
                        -- 2 local function definitions:
                        ftfn g1 (v, ngs)        =  contains v g1
                        func1 g2@(Graph(pairs)) =  Graph (filter (ftfn g2) pairs)
                      in
                        nest iterCount func1 g0