module Homework7 (main) where

import Data.List(minimumBy)
import Data.Ord(comparing)

--data Tree a = Leaf | Node (Tree a) a (Tree a)


-- Nodes are not declared explicitly. A value of type a is a node.
-- The nodes are linked by Links: (node_a, node_b)
type Link a = (a, a)
data (Eq a, Show a) =>
     Graph a = Graph {nodes :: [a], links :: [Link a]}
     deriving (Show, Eq)
-- A Graph is a collection of values (of type a) with Links joining them.

exampleGraph =
  let node1 =  1
      node2 =  2
      node3 =  3
      node4 =  4
      node5 =  5
      node6 =  6
  in Graph [node1, node2, node3, node4, node5, node6]
           [ (node1, node2)
           , (node2, node3)
           , (node2, node4)
           , (node3, node5)
           , (node5, node2)
           , (node4, node1)
           , (node5, node6)
           ]
data Tree  a = EmptyTree | Node a  [Tree a]  deriving (Show, Read, Eq)

reachableFrom :: (Show a, Eq a) => Graph a -> a -> Tree a

extendedRecursionEngine termCond termFn reduceFn mapFn wayAheadFn x =
    recursiveFn x
    where recursiveFn y
             | termCond y = termFn y
             | otherwise = reduceFn (mapFn y) (map recursiveFn (wayAheadFn y))

linksFrom :: (Eq a, Show a) => Graph a -> a -> [a]
linksFrom graph node = [n2 | (n1, n2) <- links graph, n1 == node]

reachableFrom graph startNode =
   extendedRecursionEngine
      (\ (node, expanded) -> node `elem` expanded )      -- Stop if we have already expanded this node.
      (\ (node, _) -> Node node [])  -- If we are done, construct a Tree Node with no descendents.
      Node                           -- Build a Tree Node from a graph node and the returned subtrees.
      (\ (node, _) -> node)          -- Save the graph node for the reduceFn.
      (\(node, expanded) -> [ (node', node:expanded) | node' <- linksFrom graph node ])      -- Construct a list of nodes that can be reached in one step.
                                     -- Also add the current node to expanded.
      (startNode, [])                -- Start at the start node. expanded is initially empty.


--shortestPath :: (Eq a, Show a) => Graph a -> a -> a -> Maybe [(a, a)]
-- Recall: Path = [Link] and Link = (a, a). So:
--shortestPath :: (Eq a, Show a) => Graph a -> a -> a -> Maybe (Path a)

--allPathsTo :: (Eq a) => Tree a -> a -> [[(a, a)]]
-- Recall: Path = [Link] and Link = (a, a). So:
allPathsTo :: (Eq a) => Tree a -> a -> [Path a]
-- Return a list of Paths from the tree's root to the goal.
-- If there are no paths, the list will be empty.

type Path a = [Link a]

shortestPath :: (Eq a, Show a) => Graph a -> a -> a -> Maybe (Path a)


allPathsTo tree goal =
   extendedRecursionEngine
       -- termCond
       -- Terminate if there are no children or if the goal is one of the children.
      (\(Node _ children) -> null children || goal  `elem` children )

       -- termFn
       -- If there are no children, there are no paths.
       -- If we reached the goal create a list of paths. So far there is only one path.
       -- It is the path consisting of one Link from parent to goal.
      (\ (Node parent children) -> if null children then [] else [[(parent, goal)]])
       -- ReduceFn
       -- parent is a graph node.
       -- Since each child returns a list of paths, pathss is a list of lists of paths: [[Path]]
       -- For each path in the list of lists of paths, put the Link from parent
       -- to its start node in front as the first link.
      (\ parent pathss -> map (\path -> parent : path) pathss)  --- Error Message
       -- MapFn
      (\ (Node parent _)  -> parent)      -- Keep the parent for the reduceFn.
       -- wayAheadFn
      (\ (Node _ children) -> children)   -- Pass along the list of children for the recursive calls.
      tree



-- Return the shortest path in graph from the from node to the to node.
-- Use Maybe/Just/Nothing to cover cases where there are no paths.
shortestPath graph from to = shortest (allPathsTo (reachableFrom graph from) to)

-- If xss (a list of lists) is null, return Nothing; otherwise return Just <the shortest list>


-- If xss (a list of lists) is null, return Nothing; otherwise return Just

shortest :: [[a]] -> Maybe [a]
shortest xss
   | null xss = Nothing
   | otherwise = Just (minimumBy (comparing length)  xss)
   -- For a cool way to sort, look up "sortBy" in the modules chapter.

extendedRecursionEngine ::
       (a -> Bool)        -- termCond
    -> (a -> b)           -- termFn
    -> (t -> [b] -> b)    -- reduceFn
    -> (a -> t)           -- mapFn
    -> (a -> [a])         -- wayAheadFn
    -> a                  -- input
    -> b                  -- output

For our application the type a is Tree;
                             b is [Path], i.e., a list of Paths;
                             t is graph node, which is the value component of a Tree Node.




Error Message


Homework7.hs:91:55:

    Couldn't match expected type `(t, a)'

           against inferred type `[(t, a)]'

      Expected type: [[(t, a)]]

      Inferred type: [[[(t, a)]]]

    In the second argument of `map', namely `pathss'

    In the expression: map (\ path -> parent : path) pathss