Ну конечно, ведь строки - слабое место C, вот их и исправили 1000 раз.

Давно пора на первых курсах быдловузов (имею в виду околопрограммерские специальности) проводить обязательные занятия по политинформации, на которых пудовой кувалдой вбивать в головы школоте тот факт, что от них требуется маленький шустрый бинарник, а не красивый текстовый файл с ровными отступами.

Это не относительно хаскеля, а вообще.

Мы, видимо, как-то поразному понимаем, что такое рантайм.

Поддержка кучи не обязательна.

Ты говоришь о freestanding environment, я о hosted.

Только голый код, который сразу готов для голого процессора.

А Vala тянет всю glibc в качестве рантайма.

Повторюсь - в рамках разговора freestanding неинтересен.

получается, что Haskell - самый эффективный язык для реализации Perl 6

Надо только определить удобные критерии эффективности :)

Если Вам нужно произвести поиск и найти подходящую статью что есть деревья

Я отлично знаю, что такое деревья. Проблема в том, что их очень много разных видов.

Хорошо, что такое четверичные/восьмеричные деревья я понял. Даже использовал что-то подобное, только они почему-то назывались деревьями Меркле, для расчета хешей.

Только к пониманию вопроса что такое локально-рекурсивный это меня не приблизило. Проблема не в том, что я не понимаю что такое (рекурсивный) обход дерева. Я не понимаю что вы имеете в виду под «локально-рекурсивный обход».

Но это будет дорого стоить.

Не нужно кидать дешевые понты, ладно? И без тебя в конце рабочего дня блевать тянет.

что от них требуется маленький шустрый бинарник, а не красивый текстовый файл с ровными отступами.

K&R на практике доказали обратное. В топку такие «политинформации».

1)кто то сделал 99% работы за афтара

ты код читал?

жтутф, компилятор perl6 уже давно написан на perl6 полностью.

на которых пудовой кувалдой вбивать в головы школоте тот факт, что от них требуется маленький шустрый бинарник, а не красивый текстовый файл с ровными отступами.

маленький шустрый бинарник почти никогда, по большому счету, не нужен.

Я не понимаю что вы имеете в виду под «локально-рекурсивный обход».

Е-мае... для обычного многомерного массива индексы (смещения элементов массива относительно его начала) выглядят так:

0 1 2 3 4 5 6 7 
8 9 10 11 12 13 14 15
16 17 ...

0 1 4 5 ...
2 3 6 7 ...
8 9 12 13 ...
10 11 14 15 ...
...

Не нужно кидать дешевые понты, ладно? И без тебя в конце рабочего дня блевать тянет.

Тогда нефига изображать из себя человека, который не умеет пользоваться поиском.

Почти никогда, кроме постоянно.

2

для локально-рекурсивного массива так

Т.е. как я понимаю то что ты привел описывается четверичным, вернее 2^N-ричным?

Тогда что вы понимаете под локальностью? По логике вещей это должна быть какая-то метрика, правильно? Так что это за метрика?

Что такое локально-рекурсивный ОБХОД? Чем он отличается от самого обычного обхода дерева?

который не умеет пользоваться поиском.

Я отлично умею пользоваться поиском. Но основная проблема в том, что нужны определенные исходные данные, чтобы фильтровать информационный шум. Собственно это я из тебя и пытаюсь вытянуть.

хи, на джаве это написалось бы в 3 строчки)

почему эти строчки не в твоём посте?

Что получилось

Там несколько ошибок и предупреждений - посмотри ghc -Wall you_source.hs и hlint you_source.hs.

И ещё можно сократить:

getPort = PortNumber . fromIntegral . read

repl handle = forever $ getLine >>= hPutStrLn handle >> putStr "Answer := " >> hGetLine handle >>= putStrLn

processRequest handle = hGetLine handle >>= hPutStrLn handle . prettyPrint . reads >> processRequest handle

primes = 2 : filter ((== 1) . length . primeFactors) [3, 5 ..]

Что это за вырвиглазие?

Это же вроде AIO? А в хаскеле fork-и (лёгкие процессы).

processRequest handle = hGetLine handle >>= hPutStrLn handle . prettyPrint . reads >> processRequest handle

processRequest handle = forever $ hGetLine handle >>= hPutStrLn handle . prettyPrint . reads

тоже, чтобы явную рекурсию не писать.

от них требуется маленький шустрый бинарник, а не красивый текстовый файл с ровными отступами

Programs must be written for people to read, and only incidentally for machines to execute.

А кувалдой надо тебя за дебильность.

Там несколько ошибок и предупреждений

Хм... а у меня ни одной ошибки и 8 достаточно глупых предупреждений. Хотя нет, одно действительно полезное: «In an equation for `prettyPrint': Patterns not matched: (_, _) : (_ : _)», тут он прав, надо поправить.

Это же вроде AIO? А в хаскеле fork-и (лёгкие процессы).

В плюсах это достаточно «элегантно» решается, если поверх AIO прикрутить бустовкий же threadpool.

processRequest handle = forever $ hGetLine handle >>= hPutStrLn handle . prettyPrint . reads

Это круто, согласен, но, равно как и pointfree, не особо читаемо. Но всё равно спасибо!

Мне так нравится, что по запросу гуглу «локально рекурсивный» третьей ссылкой идет эта тема на ЛОРе. =)

[fat mode]

http://pastebin.com/aq1GaVUB - программа, накатанная на быструю руку за 20 минут, из которых 15 заняло чтение документации (до этого на питоне TCPServer и argparse не юзал) решающая описанную задачу на Python - чуть меньше 60 строк и выглядит не так запутанно, как на Haskell.

Завтра посмотрю, сколько у меня выйдет строк на C++ :)

1) в нормальных дистрибутивах (tm) на подобные грабли можно наступить не чаще, чем раз в 10 лет

Хм... а у меня ни одной ошибки и 8 достаточно глупых предупреждений.

otherwise в case expression в main (otherwise = True и используется в guard expression, тут нужно _), -fno-warn-unused-do-bind можно поставить, top-level типы дописать, sieve и factor не по всем случаям расписаны, n в factor затеняет n из primeFactors (можно перепутать, получится не хорошо, лучше разные имена давать).

hlint обычно про point free и про разные liftM пишет - вопрос стиля, делать «don't make me think» (явно расписывать функции и do-нотацию) или что-то более активно использующее комбинаторы (point free в функциях, >>, >>= и разные комбинаторы из Control.Monad вместо/вместе с do-нотацией).

Первый, я так понимаю, в том, что одно и то же можно многими путями. А второй какой?

программа, накатанная на быструю руку за 20 минут

Молодец, но я бы не сказал, что выглядит «менее запутанно», чем на хаскелле, хотя кому как. Тебе ещё повезло, что из коробки многопоточный tcp-сервер оказался, в хаскелле этого нет, пришлось тривиально реализовать на том, что есть, но всё равно отлично.

1) в нормальных дистрибутивах (tm) на подобные грабли можно наступить не чаще, чем раз в 10 лет

Ну, да. Просто за тебя эту работу выполняет сотня мартышек мейнтейнеров.

http://pastebin.com/RKMKtpmm - заменил дробное деление с округлением на нормальное целочисленное

Тебе ещё повезло, что из коробки многопоточный tcp-сервер оказался

Сделать самому - это +еще несколько строк.

Первый, я так понимаю, в том, что одно и то же можно многими путями.

Да. С одной стороны ты можешь выбрать удобны для себя способ - это плюс. Но разбирать код другого человека, у которого путь другой - это большой геморрой. А для больших проектов при небольшой документированности кода это критично.

А второй какой?

Ты работал с STL? Удобная штука. Даже очень. Но вот ошибки компилятора...
Распарсишь вот это?
readply.cpp:109: conversion from ‘_List_iterator<list<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,allocator<basic_string<char,string_char_traits<char>,__default_alloc_tem
plate<true,0> > > >,const list<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,allocator<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > > > &,const list<basic_string<char,string_char_traits<char>,__default_alloc
_template<true,0> >,allocator<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > > > *>’ to non-scalar type ‘list<basic_string<char,string_char_traits<char>,__default_alloc_temp
late<true,0> >,allocator<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > > >’ requested


ВАЖНО!
Первый недостаток проявляется ТОЛЬКО в больших проектах, когда другому нужно разбирать чужой код, и в компании не стандартизированы подходы к написанию кода на C++.
Второй недостаток - скорее недостаток компилятора и проявляется ТОЛЬКО при работе с шаблонами, особенно с STL.

Ты работал с STL?

Конечно. Кстати, аналогов в других языках нет из коробки.

Распарсишь вот это? readply.cpp:109: conversion from ‘_List_iterator<list<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,allocator<basic_string<char,string_char_traits<char>,__default_alloc_tem plate<true,0> > > >,const list<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,allocator<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > > > &,const list<basic_string<char,string_char_traits<char>,__default_alloc _template<true,0> >,allocator<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > > > *>’ to non-scalar type ‘list<basic_string<char,string_char_traits<char>,__default_alloc_temp late<true,0> >,allocator<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > > >’ requested

Уже привык к этому и вполне нормально воспринимаю. И clang немного человечнее ошибки выдает.

вполне нормально воспринимаю

я тоже привык и нормально воспринимаю, но парсить эту муть - повеситься легче

И ещё исключения нужно обрабатывать, в тех случаях когда клиент будет посылать не числа. Примерно так:

import Prelude hiding ( catch )
import Control.Monad
import Control.Exception
import Control.Concurrent
import System
import System.IO
import Network

client :: String -> PortID -> IO ()
client host port = withSocketsDo $ do
  h <- connectTo host port
  hSetBuffering h NoBuffering
  forever $ getLine >>= hPutStrLn h >> hGetLine h >>= putStrLn

server :: (String -> String) -> PortID -> IO ()
server fn port = withSocketsDo $ listenOn port >>= handler
  where
    handler s = forever $ do
      (h, _, _) <- accept s
      hSetBuffering h NoBuffering
      forkIO $ onRequest h
    onRequest h = forever $ do
      line <- hGetLine h
      catch (hPutStrLn h $ fn line) $
        \(_ :: SomeException) -> hPutStrLn h $ "bad request: " ++ line

main :: IO ()
main = do
  args <- getArgs
  case args of
    ["server", port] -> server (show . fact . read) $ parsePort port
    ["client", host, port] -> client host $ parsePort port
    _ -> putStrLn "usage: fact server <port> | fact client <host> <port>"
  where
    parsePort = PortNumber . fromIntegral . read
    fact n = product [1 .. n]

Примерно так

Зачем? Там же prettyPrint $ reads line, если reads не справляется, prettyPrint просто вернёт «NaN».

- main = do
+ main = withSocketsDo $ do

Да, действительно, спасибо за замечания.

реального

клиент-серверное приложение подсчета простых чисел

О да, детка! Реальнее и злободневнее просто некуда!

Зачем?

Ну это как я сделал - server принимает функцию (String -> String), и учитывает, что она может упасть. Если зашивать надёжный разбор и обработку запроса в саму server (а не отдавать аргументом функцию обработки), или просто считать что server всегда отдадут хорошую функцию, то можно обойтись и без исключений. Как третий вариант, можно писать тотальную (String -> String):

safeHead :: [a] -> Maybe a
safeHead (x:_) = Just x
safeHead [] = Nothing

safeRead :: Read a => String -> Maybe a
safeRead = fmap fst . safeHead . reads

-    onRequest h = forever $ do
-      line <- hGetLine h
-      catch (hPutStrLn h $ fn line) $
-        \(_ :: SomeException) -> hPutStrLn h $ "bad request: " ++ line
+    onRequest h = forever $ hGetLine h >>= hPutStrLn h . fn

-    ["server", port] -> server (show . fact . read) $ parsePort port
+    ["server", port] -> server (show . fmap fact . safeRead) $ parsePort port

$ ./fact server 8080 &
[2] 3121
$ ./fact client 127.0.0.1 8080
1
Just 1
2
Just 2
3
Just 6
4
Just 24
q
Nothing
w
Nothing
^C
fact: <socket: 4>: hGetLine: end of file

(вот для типа вроде Maybe уже можно написать pretty printer, если не хочется смотреть на артефакты хаскеля в репле).

выражаться в терминах таких safe* функций лучше, чем писать конкретную safe функцию вроде prettyPrint.

Есть ещё такая вещь как readM:

readM :: (Monad m, Read a) => String -> m a
readM s | [x] <- [x | (x, _) <- reads s] = return x
        | otherwise = fail $ "Failed to parse: " ++ s

которая делает reads в произвольной монаде:

> :m + Control.Monad.Identity
> runIdentity (readM "1" :: Identity Int)
1
> runIdentity (readM "q" :: Identity Int)
*** Exception: Failed to parse: q
> readM "1" :: IO Int
1
> readM "q" :: IO Int
*** Exception: user error (Failed to parse: q)
> readM "1" :: Maybe Int
Just 1
> readM "q" :: Maybe Int
Nothing

т.е. тут чтение в Identity и IO unsafe, в Maybe - safe. С readM будет так:

server :: (Read a, Monad m) => (m a -> String) -> PortID -> IO ()
server fn port = listenOn port >>= handler
  where
    handler s = forever $ do
      (h, _, _) <- accept s
      hSetBuffering h NoBuffering
      forkIO $ onRequest h
    onRequest h = forever $ hGetLine h >>= hPutStrLn h . fn . readM

тут то, будет ли server падать на некорректных запросах определяется тем в какой монаде будет производится вычисление, если в Identity или IO - будет, в Maybe - нет:

safeFact :: Maybe Integer -> String
safeFact = show . fmap fact

...

server safeFact ...

unsafeFact :: Identity Integer -> String
unsafeFact = show . fmap fact

...

server unsafeFact ...

forever $ hGetLine h >>= hPutStrLn h . fn . readM

forever $ hPutStrLn h . fn . readM =<< hGetLine h

Так, может, немножко нагляднее. forever - бесконечный цикл последовательности действий hGetLine -> readM -(через и параметрически и ad-hoc полиморфный тип)-> fn -> hPutStrLn.

Кстати, аналогов в других языках нет из коробки.

Да, функций высшего порядка и параметрических типов нет ни в одном языке.

Т.е. как я понимаю то что ты привел описывается четверичным, вернее 2^N-ричным?

То что я привел, описывается именно четверичным. 2^N ричное дерево будет для пространства размерности N. Для одномерного случая кстати получится обычный массив.

Тогда что вы понимаете под локальностью? По логике вещей это должна быть какая-то метрика, правильно? Так что это за метрика?

Расстояние между ячейками массива в памяти. Локальность обеспечивает хорошую кэшируемость и след. высокий темп доступа к данным.

Что такое локально-рекурсивный ОБХОД? Чем он отличается от самого обычного обхода дерева?

Там речь идет не об обходе дерева а об обходе графа вычислений. Который не дерево ни разу. Дерево - это контейнер для данных, используемых графом.

Я отлично умею пользоваться поиском.

А вот и есть дешевые понты. Потому что не найти описание устоявшегося термина «восьмеричное дерево» и гнуть пальцы...

Расстояние между ячейками массива в памяти.

Точнее среднее расстояние между СОСЕДНИМИ ячейками массива в памяти. Скажем для двумерного массива M &(M(i,j)) - &(M(i+1,j)). Для каждой ячейки ищем расстояние до соседей задействованных в числ схеме при ее обработке, выбираем макс расстояние. Потом эти расстояния усредняем по всему массиву, или строим функц распред - кому что больше нравится.

Там речь идет не об обходе дерева а об обходе графа вычислений.

Т.е. мы обходим граф вычислений таким образом, чтобы порядок обхода узлов удовлетворял некому критерию локальности, а поскольку граф представлен рекурсивной структурой данных/структурно рекурсивен/рекурсивно задан (you name it), то и алгоритмы для работы с ним уместно применять рекурсивные. Поэтому и локально-рекурсивный обход. Так?

Т.е. мы обходим граф вычислений таким образом, чтобы порядок обхода узлов удовлетворял некому критерию локальности,

Да.

поскольку граф представлен рекурсивной структурой данных/структурно рекурсивен/рекурсивно задан

Нет. Граф определяется числ схемой, и не рекурсивен. Ну там же по ссылкам картиночки есть. Граф можно обходить по разному, обычно его обходят нерекурсивно, поэтому и работает все так медленно.

Где искаропки есть priority_queue<> хотя бы? :)

Раз дошло до кода, вот вам решение на питоне:

Сервер:

 
#!/usr/bin/python
from mysocket.server import *

numbers = []
for i in xrange(2,2**16-1) :
    for k in xrange(2,int(i**.5)+1) :
        if i/k*k==i : break
    else : numbers.append(i)

class Server :
    def split( self, x ) :
        if type(x) not in ( int, long ) : raise Exception('illegal type')
        if x>2**32 : raise Exception('very large number')
        res = []
        while x not in numbers :
            lim = x**.5+1
            for n in numbers :
                if n>lim : break
                if x/n*n==x : res.append(n); x /= n; break
        res.append(x); return tuple(res)

server( '127.0.0.1', ['127.0.0.1'], 1704, Server ) #run server

клиент

 
#!/usr/bin/python
from mysocket.client import *

connect = client( '127.0.0.1', 1704 )
l = raw_input('new number=')
while l : 
    print connect.split(int(l))
    l = raw_input('new number=')

mysocket описан тут http://a-iv.ru/pyart/mysocket-I.pdf правда там м.б. устаревшая версия. Да, и с т.з. производительность это не самое лучшее решение, но оно многопоточное и я его склепал за 15 мин;-)

Расстояние между ячейками массива в памяти. Локальность обеспечивает хорошую кэшируемость и след. высокий темп доступа к данным

Что-то это сильно напоминает мне http://ru.wikipedia.org/wiki/Loop_tiling

Да. Только тут это возведено в абсолют;-)

И не надо подбирать размер блока. И потом, в памяти много уровней, LRnLA позволяет эффективно использовать все. Гипотетически можно организовать многоуровневый Loop tiling и оптимально юзать все уровни, но во первых писать замучаешься, во вторых настраивать под конкретную машину, в третьих не факт что вообще получиться сделать эффективный код.