「幸いさ」の実装

code:Saiwaisa.hs

module Saiwaisa

where

import Data.List

import Data.Ord

segSplits :: Eq a => (a -> Bool) -> a -> a

segSplits _ [] = [[]]

segSplits _ a = a

segSplits p (a:as) = case segSplits p as of

bss -> map (a :) bss'' ++ map (add a) bss'

where

add x (y:ys) = (x:y):ys

bss' = filter (all p . tail) bss

bss'' = filter (p . head) bss'

palindrome :: Eq a => a -> Bool

palindrome = (==) <*> reverse

saiwaisa :: String -> Double

saiwaisa = (/) . genericLength

<*> genericLength . shortestPalindromes

shortestPalindromes :: String -> String

shortestPalindromes = minimumBy (comparing length)

. filter (palindrome . head)

. segSplits palindrome

リスト（文字列は文字のリスト）のセグメント分割を segSplits (const True) で素朴に生成すると、長さ$ N のリストに対して、$ 2^{N-1} 個の分割が生成されてしまうので、生成数を抑えるようにちょっと工夫が必要。