put the code below into a .hs file, tried to import it by ":t xx.hs", but got an error.. I suspect it's syntax problem after seeing other questions.Hopefully someone could help me out.

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
  let smallerSorted = quicksort [a | a  xs, a <= x]
       biggerSorted = quicksort [a | a  xs, a > x]
  in smallerSorted ++ [x] ++ biggerSorted

get error:

Not in scope: ‘a’ Failed, modules loaded: none.

1 Answers

5
Willem Van Onsem On Best Solutions

The indentation of the two declarations in the let clause should match, like:

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
  let smallerSorted = quicksort [a | a <- xs, a <= x]
      biggerSorted = quicksort [a | a <- xs, a > x]  -- no extra spacing
  in smallerSorted ++ [x] ++ biggerSorted

In your original question, you also forgot to use the <- operator in the generator expression part of your list comprehension: you should thus write a <- xs, instead of a xs.

You can however, as @RobinZigmond says, add spaces before and after the =, as long as you have the same number of spaces before the first non-space character, this is fine, like:

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
  let smallerSorted = quicksort [a | a <- xs, a <= x]
      biggerSorted  = quicksort [a | a <- xs, a > x]  -- extra space before =
  in smallerSorted ++ [x] ++ biggerSorted

Note that you can use partition :: (a -> Bool) -> [a] -> ([a], [a]) to split a list in two lists where the first sublist has elements that satisfy the predicate, and the latter has the elements that do not satisfy the predicate, like:

import Data.List(partition)

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
  let (smal, big) = partition (x >) xs
  in quicksort smal ++ x : quicksort big

The partition function is normally implemented in such way that it iterates only once over the given list, and only performs the test once. So this is typically (a bit) more efficient than using two list comprehensions that each individually filter the given list.