Skip to content

Instantly share code, notes, and snippets.

@abhin4v
Last active December 22, 2020 12:16
Show Gist options
  • Save abhin4v/9fc8eff25c6b1a14b60e to your computer and use it in GitHub Desktop.
Save abhin4v/9fc8eff25c6b1a14b60e to your computer and use it in GitHub Desktop.
Implementation of depth first search in Haskell
module DepthFirstSearch where
import Data.Foldable (asum)
import Data.List ((\\))
dfs :: (Eq a) => (a -> [a]) -> a -> a -> Maybe [a]
dfs next start goal = dfs' [] start
where dfs' path current
| current == goal = Just . reverse $ goal : path
| null nexts = Nothing
| otherwise = asum . map (dfs' (current : path)) $ nexts
where nexts = next current \\ path
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment