trie.hs

import Data.List

data Trie key value = Vertice value [Edge key value] deriving Show
data Edge key value = Edge key (Trie key value) deriving Show

example :: Trie Char Integer
example = Vertice 0 [
	Edge 'h' $ Vertice 0 [
		Edge 'e' $ Vertice 1 [], 
		Edge 'i' $ Vertice 0 [
			Edge 's' $ Vertice 3 []
			]
		],
	Edge 's' $ Vertice 0 [
		Edge 'h' $ Vertice 0 [
			Edge 'e' $ Vertice 2 []
			]
		]
	]

lookup' :: Eq a => [a] -> Trie a b -> Maybe b
lookup' [] (Vertice value edges) = Just value
lookup' (step:path) (Vertice _ edges) = find (\(Edge k v) -> k == step) edges >>= 
	\(Edge key vertice) -> lookup' path vertice

main = print $ lookup' "his" example