blob: 2bfdb4a3af4aa4011d1399d53a82eab185b52a59 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
module Pancake (
pancakeSort
) where
pancakeSort :: Ord a => [a] -> [a]
pancakeSort [] = []
pancakeSort cakeStack =
let selectedCake = indexOfLargest cakeStack
cakeStack' = (doFlip (length cakeStack)) . (doFlip selectedCake) $ cakeStack
in (pancakeSort (init cakeStack')) ++ [last cakeStack']
indexOfLargest :: Ord a => [a] -> Int
indexOfLargest (x:xs) =
let f m i j y = if length y == 0
then i
else if (head y) > m
then f (head y) j (j+1) (tail y)
else f m i (j+1) (tail y)
in f x 0 1 xs
doFlip :: Int -> [a] -> [a]
doFlip depth list =
let prefix = take (depth + 1) list
rest = drop (depth + 1) list
in (reverse prefix) ++ rest
|
