CODEWITHSUNDEEP
haskelloptimization
Adam
Adam

Reputation: 3013

Haskell recursion slow, what's the pitfall?

I'm very much a beginner in Haskell

data Recipes = Recipes Int Int Int [Int] deriving(Show) 

addRecipes :: Recipes -> Recipes
addRecipes (Recipes t e1 e2 list) = 
    let (e1c, e2c) = (list !! e1, list !! e2)
        newVal = e1c + e2c
        newList = list ++ (digits $ newVal)
        e1n = calcNewPos e1 e1c newList
        e2n = calcNewPos e2 e2c newList
    in Recipes t e1n e2n newList

calcNewPos :: Int -> Int -> [Int] -> Int    
calcNewPos i i2 list = (i + i2 + 1) `mod` (length list)

-- Borrowed:
-- https://stackoverflow.com/questions/3963269/split-a-number-into-its-digits-with-haskell
digits :: Int -> [Int]
digits = map (read . (:[])) . show

The above piece of code is part of a recursion which I omitted. The addRecipes is called again and again in a recursive call. This is a solution to an advent of code problem (AoC 2018 day 14). The code produces the correct result but is cripplingly slow.

I'm just trying to learn where the problem lies, what is horribly inefficient in the code above?

I've tried optimizing away the ++-operator and replace it with a : and combining things with the digits call. I know the ++ is slower than the : but is that really it? (Remember, i'm learning Haskell so I want to fix this code if possible and know why I can't write it like this)

Edit: The list in Recipes grows and becomes large

Upvotes: 1

Views: 193

Answers (1)

Adam
Adam

Reputation: 3013

I followed the advice posted in the comments; Do not use a the list data structure when you make a lot of random accesses. So I replaced the list with with Sequence http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Sequence.html

import qualified Data.Sequence as Seq

data Recipes = Recipes Int Int Int (Seq.Seq Int) deriving(Show) 

addRecipes :: Recipes -> Recipes
addRecipes (Recipes t e1 e2 seq) = 
let (e1c, e2c) = (Seq.index seq e1, Seq.index seq e2)
    newVal = e1c + e2c
    newSeq = (Seq.><) seq (Seq.fromList (digits newVal))
    e1n = calcNewPos e1 e1c newSeq
    e2n = calcNewPos e2 e2c newSeq
in Recipes t e1n e2n newSeq

calcNewPos :: Int -> Int -> (Seq.Seq Int) -> Int    
calcNewPos i i2 seq = (i + i2 + 1) `mod` (Seq.length seq)

It worked and the run time is now reasonable (from 1 hour to seconds). Thanks commenters!

Upvotes: 1

Related Questions