Naive implementation of Burst Balloon
First of all, it's great that you've used type signatures for all your functions. Also, all used functionality is hidden away in helpers, which is also a plus.



We can rewrite burstNative with  maximumBy and comparing:

import Data.List (maximumBy)
import Data.Ord (comparing)

burstNaive :: [Int] -&gt; (Int, IndexOrder)
burstNaive [] = (0, [])
burstNaive xs = maximumBy (comparing fst) . allOrders $ xs


While it's possible to use ((0, []) . allOrders instead of the pattern matching, matching makes the base case more visible.

Also, this is a perfect spot to use IndexOrder instead of [Int].



In withOrder we traverse the list too often. Since lists are just forward linked lists in Haskell, we have to walk through the list four times, once for left, once for right, once for xs !! i and once for splitAt. That's a handful. So instead let's do that only once:

-- def: default value if list is too short/at end
moveAtStencil3 :: a -&gt; Int -&gt; [a] -&gt; ((a,a,a), [a])
moveAtStencil3 def i xs 
   | i &lt; 1     = let (m:r:_) = xs in ((def, m, r), drop 1 xs)
   | otherwise = let (as,bs) = splitAt (i - 1) xs
                     (l:m:r) = take 3 (bs ++ repeat def) 
                 in ((l,m,r), as ++ (l : r : drop 3 bs)

withOrder :: IndexOrder -&gt; [Int] -&gt; Int
withOrder []     _  = 0
withOrder (i:is) xs = left * middle * right + withOrder adjusted xss
  where
    ((left, middle, right), xss) = moveAtStencil3 1 i xs
    adjusted = map (\index -&gt; if index &gt; i then index - 1 else index) is


While we're at it, I renamed adjust to adjusted. Verbs (adjust) are usually functions, whereas adjusted is a list.



We could replace permutations in allOrders with recursion, but that wouldn't change much.