Writing recursion properly

Learn
#1

Hello, I’m very new to Haskell and to functional programming in general. I have a question about writing recursive functions - namely that I find myself writing ‘helper’ functions to pass state around. I do this in imperative languages as well, but I was wondering if Haskell had some sugar or otherwise to mitigate this? As an example, here is some code I’ve written to replicate the ‘stride’ syntax in eg python [start:end:stride]

-- Gentle replication of indexing syntax from imperative languages
getIndex :: [Char] -> Int -> Char
getIndex list 0 = head list
getIndex (x:xs) idx
    | idx > (length (x:xs)) = ' '
    | otherwise = getIndex xs (idx - 1)


-- The accumulated word, the source word, the index, the stride
getStrideHelper :: String -> String -> Int -> Int -> String
getStrideHelper acc src idx stride
    | idx >= length src = acc
    | otherwise = getStrideHelper ((getIndex src idx):acc) src (idx + stride) stride


-- The source word, the starting index, the stride
getStride :: String -> Int -> Int -> String
getStride word start_idx stride = reverse (getStrideHelper "" word start_idx stride)

Any and all comments / advice / criticism appreciated!

Thank you!

#2

I think it is normal to use a helper function with more parameters than the public one. Using a second function with extra parameters is commonly used to achieve tail recursion.

If possible, it is better to use higher-order functions instead of writing the recursion yourself. This is called wholemeal programming and getStride could be something like

getStride word start_idx stride = snd . unzip . (filter (\(x,_) -> mod x stride == 0)) . (zip [0..]) . (drop start_idx) $ word
3 Likes
#3

Welcome @atombear!

As far as “sugar” to mitigate these helper functions, I’ve commonly seen the helper functions defined as local functions, so like

-- The source word, the starting index, the stride
getStride :: String -> Int -> Int -> String
getStride word start_idx stride = reverse (go "" start_idx)
  where
  go acc idx
    | idx >= length word = acc
    | otherwise = go (getIndex word idx : acc) (idx + stride)
  
  getIndex str idx = fromMaybe ' ' $ listToMaybe $ drop idx str

Another option is to use foldl' or foldr, which can let you replace some helper recursive function with just a lambda:

-- The source word, the starting index, the stride
getStride :: String -> Int -> Int -> String
getStride word start_idx stride = 
  foldr (\idx acc -> getIndex word idx : acc) "" idxs

  where  
  idxs = takeWhile (< length word) [start_idx, start_idx+stride .. ]
  getIndex str idx = fromMaybe ' ' $ listToMaybe $ drop idx str

All that said, @ilkecan’s approach is a lot more idiomatic for Haskell, and wholemeal programming for lists is a lot more powerful and becomes more intuitive the more you use Haskell. In the long run, you’ll be more productive if you try to get used to wholemeal programming more, but there’s nothing wrong with doing manual recursion or folds, so the most important thing for learning Haskell is to just keep writing Haskell code! (Don’t fall into the trap of just trying to read more about Haskell until everything “clicks”)

#4

thank you for replying - very informative! i did for several months refrain from writing actual code as i tried to internalize everything i could about monads and functors… i figured it would make sense eventually and now i’m writing code.

i will read these responses and internalize them!

1 Like