Hello all <div>I am trying to implement depth search in Haskell.  My issue here is kind of backtracking.  Haskell code for depth first search </div><div><br></div><div><div>import Data.List</div><div>import Data.Array</div>
<div>import Control.Monad</div><div><br></div><div><br></div><div>type Node = Int </div><div>type Graph = Array Int [  Node  ]  </div><div><br></div><div>dfs&#39; ::  Graph -&gt; Node -&gt; [ Node ] -&gt; [ Node ] </div><div>
dfs&#39; g v vis = dfsfun lst where </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>lst = g ! v </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>dfsfun [] = vis </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>dfsfun ( x : xs ) </div>
<div><span class="Apple-tab-span" style="white-space:pre">        </span>  | elem x vis = dfsfun xs </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>  | otherwise =  dfs&#39; g y ( v : vis ) </div><div><br>
</div><div>--set the flag true if the graph is direct otherwise false </div><div>buildGraph :: ( Int , Int ) -&gt; [ ( Node , Node ) ] -&gt; Bool -&gt;  Graph </div><div>buildGraph bnds xs f </div><div><span class="Apple-tab-span" style="white-space:pre">        </span> | f =  accumArray ( flip (:) ) []  bnds xs  --direct graph a-&gt;b</div>
<div><span class="Apple-tab-span" style="white-space:pre">        </span> | otherwise = accumArray ( flip (:) ) []  bnds xss where   --indirect a -&gt; b and b -&gt; a </div><div><span class="Apple-tab-span" style="white-space:pre">                </span>xss =  foldr ( \ ( x , y ) b -&gt; ( y , x ) : b ) xs xs    </div>
<div><br></div><div>dfsSearch :: Graph -&gt; Int -&gt; [ Node ] </div><div>dfsSearch g v = dfs&#39; g v [] </div><div><br></div><div>Lets create a indirect graph </div></div><div><div>ghci&gt;let g = buildGraph  ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 4 ) ] False</div>
<div>ghci&gt;g</div><div>array (0,5) [(0,[4,3,2,1]),(1,[0]),(2,[0]),(3,[0]),(4,[0]),(5,[])]</div></div><div><br></div><div><div>ghci&gt;dfsSearch g 0</div><div>[0]</div></div><div>Here  I am getting only 0 but  it should return [ 0 , 1 , 2 , 3 , 4 ] . What is happening here when i am passing  0 as root node to function , at first level i get </div>
<div> lst = [ 4 , 3, 2, 1 ]  . First element of this list is 4 so 0 is added to vis list and now 4 is passed to dfs&#39; as parent. When it goes down , we get lst = [0] and since 0 is member of vis list so it returns the vis as result .  When we write dfs in c/c++ then it returns to calling function and again loops through remaining element which i am not able visualize in Haskell.  Could some one please help me how to solve this issue . </div>
<div><br></div><div>Regards </div><div>Mukesh Tiwari</div><div><br></div>