Route.hs

mkFreshRoute :: (Functor f) => URL -> (Maybe a -> f a) -> [Int] -> f (RouteState a)
mkFreshRoute url@(URL v) f = \case
  [] -> Terminal . RouteEnd . (url,) <$> f Nothing
  (ix : ixes) -> let next = mkFreshRoute url f ixes in
    NonTerminal Nothing <$> case v V.! ix of
      Capture _      -> This . WildcardLink <$> next
      NonCapture lit -> That . LiteralLink . HM.singleton lit <$> next

-- You made the very good move of isolation out "next = mkFreshRoute url f ixes" i.e. "next = simple recursive call on ixes"
-- so the rest is easy:

mkFreshRoute url@(URL v) f = foldr z op
  where
    z = Terminal . RouteEnd . (url,) <$> f Nothing
    op ix next =
        NonTerminal Nothing <$> case v V.! ix of
            Capture _      -> This . WildcardLink <$> next
            NonCapture lit -> That . LiteralLink . HM.singleton lit <$> next