foreach( [ X | C ], S, Something ) -> foreach( C, Something( X, S ), Something );
foreach( [], S, _ ) -> S

G>Так я и предполагал, но говорить не стал — вдруг ошибусь? Ее все-таки в восемь раз активнее читать приходится, это не могло не повлиять на производительность. Но того, что это единственный значимый фактор, я, конечно, не ожидал. Прикольно.

import Data.Word
import Data.Array.MArray
import Data.Array.IO

type Atype = IOUArray Word32 Word8

newIOArray::(Word32, Word32) -> Word8 -> IO Atype
newIOArray = newArray

size::Word32
size = 100000000

{-# INLINE delete_elems #-}

delete_elems::Atype->Word32->Word32->IO Atype
delete_elems array i fi
    | i >= size = return array
    | otherwise =
        do
          writeArray array i 1
          delete_elems array (i+fi) fi

{-# INLINE sieve #-}

sieve::Atype->Word32->IO Atype
sieve array i
    | i == size = return array
    | otherwise =
        do
          elem <- readArray array i
          array <- if (elem == 0) then delete_elems array (i*2) i else return array
          sieve array (i+1)

main = 
    do
      array <- newIOArray (1,size) 0
      array <- sieve array 2
      return ()

G>Функциональный стиль это теперь, как и всегда, в первую очередь — отсутствие побочных эффектов, а не наличие рекурсии со встроенными списками или отсутствие слова for в языке. Не зачто, всегда пожалуйста .

G>Кстати, слепенький я наверно. Ну не вижу я цикла for в твоем коде. А вот list comprehensions вижу, как и отсутствие побочных эффектов.

G>def qsort(aList): 
G>        if not aList: 
G>                return [] 
G>        ltList=[y for y in aList[1:] if y<aList[0]] 
G>        gtList=[y for y in aList[1:] if y>=aList[0]] 
G>        return qsort(ltList)+[aList[0]]+qsort(gtList) 
G>

static void Main(string[] args)
{
    List<int> list = new List<int>(new int[]{ 2, 5, 1, 4, 3, 9, 4, 7});

    List<int> result = QuickSort<int>(list);
    result.ForEach(delegate(int elem) { Console.WriteLine(elem); });
}

static List<T> QuickSort<T>(List<T> list) where T : IComparable<T>
{
    if (list.Count <= 1)
        return list;
    T mid = list[list.Count / 2];
    List<T> ltList = list.FindAll(delegate(T elem) { return elem.CompareTo(mid) < 0; });
    List<T> eqList = list.FindAll(delegate(T elem) { return elem.CompareTo(mid) == 0; });
    List<T> gtList = list.FindAll(delegate(T elem) { return elem.CompareTo(mid) > 0; });
    return Concatenate(QuickSort<T>(ltList), eqList, QuickSort<T>(gtList));
}

static List<T> Concatenate<T>(params List<T>[] lists)
{
    List<T> result = new List<T>();
    foreach (List<T> list in lists)
        result.AddRange(list);
    return result;
}

G>Что характерно, если ты добавишь в любой язык встроенные списки так, как это сделано в современных ФЯ, то на нем сразу станет удобно писать в функциональном стиле. Одного не понимаю, каким именно образом это порочит "светлую идею" ФЯ?