Переполнение стека в Haskell

Question

Я пишу генетический алгоритм для генерации строки "helloworld". Но функция evolve создает переполнение стека, когда n равно 10000 или более.

module Genetics where

import Data.List (sortBy)
import Random (randomRIO)
import Control.Monad (foldM)

class Gene g where
    -- How ideal is the gene from 0.0 to 1.0?
    fitness :: g -> Float

    -- How does a gene mutate?
    mutate :: g -> IO g

    -- How many species will be explored?
    species :: [g] -> Int

orderFitness :: (Gene g) => [g] -> [g]
orderFitness = reverse . sortBy (\a b -> compare (fitness a) (fitness b))

compete :: (Gene g) => [g] -> IO [g]
compete pool = do
    let s = species pool
    variants <- (mapM (mapM mutate) . map (replicate s)) pool
    let pool' = (map head . map orderFitness) variants
    return pool'

evolve :: (Gene g) => Int -> [g] -> IO [g]
evolve 0 pool = return pool
evolve n pool = do
    pool' <- compete pool
    evolve (n - 1) pool'

При species pool = 8 пул из 8 генов реплицируется в 8 групп. Каждая группа мутирует, и наиболее подходящие из каждой группы отбираются для дальнейшей эволюции (до 8 генов).

GitHub

Answer 1

Если вы заинтересованы в производительности, я бы использовал быстрый генератор случайных чисел, такой как:

• Случайный пакет mersenne

Во-вторых, compete выглядит очень подозрительно, так как совершенно лениво, несмотря на строительство некоторых потенциально больших структур.Попробуйте переписать его, чтобы он был немного строже, используя молоток deepseq :

import Control.DeepSeq    

compete :: (Gene g, NFData g) => [g] -> IO [g]
compete pool = do
    let s = species pool
    variants <- (mapM (mapM mutate) . map (replicate s)) pool
    let pool' = (map head . map orderFitness) variants
    pool' `deepseq` return pool'

Однако ни один из этих компонентов не должен быть в IO (отдельная проблема).Что-то вроде Rand монады может быть более подходящим .

Answer 2

Благодаря предложению Дона deepseq я смог сузить проблему до mapM mutate, что вызвало слишком много громов. В новой версии mutate', которая использует seq для предотвращения тункинга.

module Genetics where

import Data.List (maximumBy)
import Random (randomRIO)

class Gene g where
    -- How ideal is the gene from 0.0 to 1.0?
    fitness :: g -> Float

    -- How does a gene mutate?
    mutate :: g -> IO g

    -- How many species will be explored in each round?
    species :: [g] -> Int

best :: (Gene g) => [g] -> g
best = maximumBy (\a b -> compare (fitness a) (fitness b))

-- Prevents stack overflow
mutate' :: (Gene g) => g -> IO g
mutate' gene = do
    gene' <- mutate gene
    gene' `seq` return gene'

drift :: (Gene g) => [[g]] -> IO [[g]]
drift = mapM (mapM mutate')

compete :: (Gene g) => [g] -> IO [g]
compete pool = do
    let islands = map (replicate (species pool)) pool
    islands' <- drift islands
    let representatives = map best islands'
    return representatives

evolve :: (Gene g) => Int -> [g] -> IO [g]
evolve 0 pool = return pool
evolve n pool = compete pool >>= evolve (n - 1)

GitHub

Answer 3

Вместо использования (map head . map orderFitness), где orderFitness - это sortBy, вы можете использовать maximumBy и один map.Это не сильно экономит (так как вы переходите от O (n log n) к O (n) и, возможно, получаете еще один фактор от устранения двойной карты), но по крайней мере несколько проще и эффективнее,Вы также избавились бы от вызова, чтобы полностью изменить.

Сомневаюсь, что это исправит проблему без deepseq, но, тем не менее, это должно быть улучшение.

Редактировать: если бы стандартная библиотека и GHC были безупречны, то head . sortBy выдаст код, идентичный maximumBy, а map head . map sortBy выдаст код, идентичный map (head . sortBy) К сожалению, ни одна из этих вещей не можетправда на практике.sortBy будет иметь тенденцию делать кучу дополнительного выделения памяти, потому что это алгоритм «разделяй и властвуй».Комбинирование карт - это оптимизация, которую вы иногда получаете, но на нее не стоит рассчитывать.

Что более важно, использование maximumBy более декларативно.Проще увидеть, что делает код и сколько времени это займет.Также должно быть легче воспользоваться преимуществами оптимизации, потому что мы знаем, какова цель, а не только как мы ее достигаем.