スマホのパターンロックの場合の数をHaskellで計算した

import Data.List as L
import Data.Map as M

type Vertex = Int
type Route = [Vertex]
type ReverseRoute = Route
type Candidate = Map Vertex [Vertex]

cand :: Candidate
cand = M.fromList
[(0, [1, 3, 4, 5, 7]),
(1, [0, 2, 3, 4, 5, 6, 8]),
(2, [1, 3, 4, 5, 7]),
(3, [0, 1, 2, 4, 6, 7, 8]),
(4, [0, 1, 2, 3, 5, 6, 7, 8]),
(5, [0, 1, 2, 4, 6, 7, 8]),
(6, [1, 3, 4, 5, 7]),
(7, [0, 2, 3, 4, 5, 6, 8]),
(8, [1, 3, 4, 5, 7])]

makeNextVertexs :: Vertex -> Route -> [Vertex]
makeNextVertexs vertex route = cand M.! vertex L.\ route

stepRoute :: ReverseRoute -> Maybe [ReverseRoute]
stepRoute route =
let
nowVertex = head route
nextVertexs = makeNextVertexs nowVertex route
in
if L.null nextVertexs
then Nothing
else Just $ L.map (\p -> p:route) nextVertexs

startToEnd :: Vertex -> [Route]
startToEnd vertex =
let
loop :: ReverseRoute -> [ReverseRoute]
loop route = case stepRoute route of
Just routes -> concatMap loop routes
Nothing -> [route]
in
L.map reverse $ loop [vertex]

subRoutes :: Route -> [Route]
subRoutes = drop 4 . inits

startWith :: Vertex -> [Route]
startWith = concatMap subRoutes . startToEnd

main :: IO ()
main =
print $
4 * length (startWith 0) + 4 * length (startWith 1) + length (startWith 4)