Advent of Code 2018 day 1 part 2: find the first repeated number after some increases and decreases
Small things

Data.List.Split

I don't see the need for this module. I see what you're going for with splitOn "\n", however Haskell has a function in Prelude called lines:

words :: String -&gt; [String]

Prelude&gt; lines "test\nphrase, please\nignore"
["test","phrase, please","ignore"]


parseString

I think it's cleaner to instead first parse your input into an Integer format and then use [Integer] everywhere instead of [String]. This simplifies your parsing and also gives you a more general function. Note that my implementation is a partial function.

parseInt :: String -&gt; Integer
parseInt (op:s) =
  case op of
    '+' -&gt; read s
    '-' -&gt; (-1) * read s
    -- There is a hole here: this will error if 'op'
    -- (the first character) isn't '+' or '-'


Return values

The type of findFreq is

findFreq :: Integer -&gt; [Integer] -&gt; [String] -&gt; (Integer, Integer, [Integer])


I see no reason why it can't return a single Integer. Perhaps you returned all values to debug initially, but once that's done you should switch back.

It also seems to me like you were using 0 as an "error value," which is appropriate in other languages but generally frowned upon in Haskell. In this case, you can instead use Maybe to indicate failure and change your type signature to

findFreq :: Integer -&gt; [Integer] -&gt; [String] -&gt; Maybe Integer


Like I mention later, this isn't necessary since we can condense and fix some logic, but I would recommend using Maybe instead in the future.

curr and acc

You do some switching around with your variables curr and acc which confused me a bit. I'd keep acc as the accumulation value for your frequency everywhere and call the list of visited values something like seenFreqs or prevFreqs.

Correctness

Repeating frequencies of 0

Your code currently assumes the repeated frequency is the first nonzero repeated frequency. Thus, it fails for the +1, -1 test case. You could change the code to

findRepeatingFrequency :: Integer -&gt; [Integer] -&gt; [String] -&gt; Integer
findRepeatingFrequency init nums xs =
  let (found, acc, lst) = findFreq init nums xs
  in found


to accommodate that.

This breaks your way of going through the list again if you don't find a repeat the first time, but fortunately there's a less obfuscated way to avoid your checking and continue: you can use cycle, which creates an infinite list consisting of the input list repeated infinitely.

cycle :: [a] -&gt; [a]

Prelude&gt; take 20 $ cycle [1,2,3,4]
[1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]


You can call findRepeatingFrequency on cycle input to prevent having to do the cycling yourself in the function.

Efficiency

Things go wrong for efficiency in findFreq. There are two problem points that make your code asymptotically inefficient.

First, in the following line

  in if next `elem` acc


elem is an O(n) operation. You're calling it for each of the n elements in your input list, meaning that your function is at least O(n^2) (and it turns out that this is the final complexity).

I checked the number of iterations required for my sample input and it took 142991 iterations to find a repeated frequency. An O(n^2) runtime is going to require about 10 billion iterations for the lookups alone. Ouch.

Second is a more insidious mistake that is easy to overlook. In this line,

   else let f = acc ++ [next]


Appending to a list is an O(n) operation. Lists in Haskell are implemented as linked lists, and appending to the back of one cannot be amortized to O(1) like one might in Python's list or Java's ArrayList. You need to travel all the way to the back to add in a link.

Fixing the second issue actually isn't very hard since you don't care about the ordering of the list. You can switch it to

   else let f = next : acc


to return to O(1) inserts.

Fixing the lookups, however, requires a change of data structure.

Introducing Data.Set

Data.Set provides unordered sets with O(log n) lookup and insert time. Yeah, it's O(log n), but the total runtime for me when I checked the implementation was less than a second.

I'm including a sample implementation of day 1 below that I've tested and confirmed on my inputs if you want to compare. However, you said you wanted pointers, so here's the pointers I'll give.


You can keep your code mostly the same (although I'd recommend making the style changes I suggested)
You will want to use two functions from Data.Set: member and insert.
Your end result will look a lot like a fold but with some differences in end conditions (kind of like findFreq)


Sample implmentation

Finally, here's a sample implementation.

module Main where

import Data.Set (Set)
import qualified Data.Set as S

-- This is a partial function
parseInt :: String -&gt; Integer
parseInt (op:s) =
  case op of
    '+' -&gt; read s
    '-' -&gt; (-1) * read s
    -- There is a hole here, assuming valid input

findRepeatingFrequency :: Integer -&gt; Set Integer -&gt; [Integer] -&gt; Integer
findRepeatingFrequency acc seen (x:xs) =
  if acc `S.member` seen
     then acc
     else findRepeatingFrequency (acc + x) (S.insert acc seen) xs

partOne :: [Integer] -&gt; Integer
partOne = sum

partTwo :: [Integer] -&gt; Integer
partTwo ints = findRepeatingFrequency 0 S.empty $ cycle ints

main :: IO ()
main = do
  file &lt;- readFile "input.txt"
  let input = filter (not . null) $ words file
  let ints = map parseInt input
  print $ partOne ints
  print $ partTwo ints