Looking for self-referential sentences

ShaSearch.hs

module ShaSearch where

import System.Process (readProcess)

-----------------------------------------------
-- Using the list monad to generate all the
-- hexadecimal words of a given length

-- All the hexadecimal characters
hexa :: [Char]
hexa = "0123456789abcdef"

-- Generate all the hexadecimal words of a given
-- length
allHexaWords :: Int -> [String]
allHexaWords n = mapM (const hexa) [1..n]


-----------------------------------------------
-- Having fun with it

-- The goal is to find a string that makes this sentence true.
sentence :: String -> String
sentence str = "The SHA-256 hash of this sentence begins with " ++ str ++ "."

-- We define a way to run sha256sum on a string
-- and get the checksum back
sha256sum :: String -> IO String
sha256sum = readProcess "sha256sum" []

-- A string makes the sentence true precisely if its checksum
-- starts with the expected hexadecimal word
check :: String -> IO (Maybe String)
check str = do
  sum <- sha256sum (sentence str)
  let matches = take (length str) sum == str
  pure (if matches then Just str else Nothing)

-- First looks for the first input for which the
-- computation returns a Just
first :: (a -> IO (Maybe b)) -> [a] -> IO (Maybe b)
first p [] = pure Nothing
first p (a : as) = do
  mb <- p a
  case mb of
    Nothing -> first p as
    Just _  -> pure mb

-- Find the first hexadecimal word of a given size
-- making the sentence hold true
search :: Int -> IO (Maybe String)
search = first check . allHexaWords

-- Find the smallest hexadecimal word bigger than 'n'
-- making the sentence hold true.
smallest :: Int -> IO (Maybe String)
smallest n = first search [n..]